/* BTP library - Banana Tree Protocol
* Copyright (C) 1999-2001 The Regents of the University of Michigan
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Library General Public
* License as published by the Free Software Foundation; either
* version 2 of the License, or (at your option) any later version.
*
* This library 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
* Library General Public License for more details.
*
* You should have received a copy of the GNU Library General Public
* License along with this library; if not, write to the
* Free Software Foundation, Inc., 59 Temple Place - Suite 330,
* Boston, MA 02111-1307, USA.
*/
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
#include <unistd.h>
#include <limits.h>
#include <errno.h>
#include <glib.h>
#include <gnet/gnet.h>
#include "btp_debug.h"
#include "util.h"
#include "b_conn_connect.h"
#include "b_conn_handler.h"
#include "btp_proto.h"
#include "btp_node.h"
#include "b_packet.h"
#define STR(S) ((S)?(S):("<NULL>"))
static void btp_conn_connect (BConn* conn, gpointer user_data);
static void btp_conn_ping (BConn* conn, gpointer user_data);
static void btp_conn_writeable (BConn* conn, gpointer user_data);
static void btp_conn_close (BConn* conn, gpointer user_data);
static void btp_conn_fail (BConn* conn, gpointer user_data);
BConnFuncs btp_proto_funcs =
{
btp_conn_connect,
btp_conn_ping,
btp_conn_writeable,
btp_conn_close,
btp_conn_fail /* TODO: Write a close function ? */
};
static void node_fail_or_leave (BtpNode* node);
static void add_handlers (BtpNode* node);
static void remove_handlers (BtpNode* node);
static void receive_any (BConn* conn, BPacket* packet, gpointer user_data);
static void receive_ok_switch (BConn* conn, BPacket* packet, gpointer user_data);
static void receive_error_switch (BConn* conn, BPacket* packet, gpointer user_data);
static void receive_ucast (BConn* conn, BPacket* packet, gpointer user_data);
static void receive_mcast (BConn* conn, BPacket* packet, gpointer user_data);
static void receive_request_neighbors (BConn* conn, BPacket* packet, gpointer user_data);
static void receive_reply_neighbors (BConn* conn, BPacket* packet, gpointer user_data);
static void receive_join (BConn* conn, BPacket* packet, gpointer user_data);
static void receive_switch (BConn* conn, BPacket* packet, gpointer user_data);
static void receive_leave (BConn* conn, BPacket* packet, gpointer user_data);
static void schedule_request_neighbors (BtpTree* tree, gboolean soon);
static void cancel_request_neighbors (BtpTree* tree);
static gboolean request_neighbors_cb (gpointer data);
static void schedule_find_new_parent (BtpTree* tree);
static gboolean find_new_parent_cb (gpointer data);
static BtpNode* find_new_parent (BtpTree* tree);
static BtpNode* find_follow_node (BtpTree* tree);
/* Switching */
static gboolean switch_timeout_cb (gpointer data);
static void schedule_switch_timeout (BtpTree* tree);
static void cancel_switch_timeout (BtpTree* tree);
/* Sequence numbers */
static gboolean seq_num_check (BtpNode* node, BPacket* packet);
/* Shortcuts */
static void schedule_find_new_shortcut_timeout (BtpTree* tree);
static gboolean find_new_shortcut_cb (gpointer data);
static void find_new_shortcut (BtpTree* tree);
static gboolean is_good_shortcut (BtpNode* node);
static void add_shortcut (BtpTree* tree, BtpNode* node);
static gboolean shortcut_ping_timeout_cb (gpointer data);
static void receive_shortcut_add (BConn* conn, BPacket* packet, gpointer user_data);
static void receive_ok_shortcut (BConn* conn, BPacket* packet, gpointer user_data);
static void receive_error_shortcut (BConn* conn, BPacket* packet, gpointer user_data);
static void receive_shortcut_remove (BConn* conn, BPacket* packet, gpointer user_data);
static gboolean shortcut_add_timeout_cb (gpointer data);
/* Node info / RDP */
static void send_node_info (BtpTree* tree);
static void schedule_send_node_info (BtpTree* tree);
static gboolean send_node_info_cb (gpointer data);
static void receive_reply_node (BConn* conn, BPacket* packet, gpointer user_data);
#define TREE (node->tree)
/* ************************************************************ */
gboolean
btp_peer_handler (BConn* bconn, gpointer user_data)
{
BtpTree* tree;
BtpNode* node;
g_return_val_if_fail (bconn, TRUE);
g_return_val_if_fail (bconn->conn, TRUE);
BTPP (1, "btp_peer_handler %s:%u (%p)\n",
bconn->conn->hostname, bconn->conn->port, bconn);
tree = (BtpTree*) user_data;
node = btp_tree_find_node (tree, bconn->conn->hostname, bconn->conn->port);
/* If we have the node, check whether we are already connected */
if (node)
{
/* Ignore if connected */
if (node->conn && b_conn_is_connected(node->conn))
{
return TRUE;
}
/* Save if not connected or connecting */
else
{
if (node->conn)
{
BTPP (1, "btp_peer_handler: deleting conn %p\n", node->conn);
b_conn_delete (node->conn);
}
bconn->group = (BGroup*) tree;
bconn->funcs = &btp_proto_funcs;
bconn->user_data = node;
node->conn = bconn;
BTPP (1, "btp_peer_handler: setting conn %p\n", bconn);
}
}
/* Otherwise, create a new node */
else
{
bconn->group = (BGroup*) tree;
node = btp_node_new (tree, bconn->conn->hostname, bconn->conn->port, bconn);
}
g_assert (bconn->group != NULL);
add_handlers (node);
++tree->num_connect;
return FALSE;
}
void
btp_proto_init (BtpTree* tree)
{
BTPP (1, "btp_proto_init\n");
if (tree->me == tree->root)
{
/* Start sending node info */
schedule_send_node_info (tree);
/* Root won't look for shortcuts, but will accept shortcuts from
others */
}
}
static void
btp_conn_connect (BConn* conn, gpointer user_data)
{
BtpNode* node = (BtpNode*) user_data;;
g_return_if_fail (conn);
g_return_if_fail (node);
g_return_if_fail (TREE);
BTPP (1, "btp_conn_connect\n");
add_handlers (node);
/* If this is my parent, send it a JOIN and request the siblings
request. */
if ( btp_tree_is_parent(node) )
{
BPacket* join_packet;
/* Send a JOIN */
join_packet = b_packet_new_join (node);
b_conn_send_packet (node->conn, join_packet);
BTPP (7, "SEND JOIN %s:%d\n", node->hostname, node->port);
/* Schedule a neighbor request. */
schedule_request_neighbors (TREE, TRUE);
/* Start sending node info */
send_node_info (TREE);
schedule_send_node_info (TREE);
/* Start looking for shortcuts */
schedule_find_new_shortcut_timeout (TREE);
}
}
static void
btp_conn_ping (BConn* bconn, gpointer user_data)
{
g_return_if_fail (bconn);
g_return_if_fail (bconn->conn);
}
static void
btp_conn_writeable (BConn* conn, gpointer user_data)
{
BtpNode* node = (BtpNode*) user_data;;
BTPP (1, "btp_conn_writeable\n");
g_return_if_fail (conn);
g_return_if_fail (node);
g_return_if_fail (TREE);
}
static void
btp_conn_close (BConn* conn, gpointer user_data)
{
/* Closing and failing are basically the same things. */
btp_conn_fail (conn, user_data);
}
static void
btp_conn_fail (BConn* conn, gpointer user_data)
{
BtpNode* node = (BtpNode*) user_data;
g_return_if_fail (conn);
g_return_if_fail (node);
g_return_if_fail (!TREE || (TREE->me != node));
/* This function gets call though b_conn_close/btp_conn_close when a
node is deleted, a connection closes, or a a node fails. */
BTPP (1, "btp_conn_fail\n");
/* Remove _ALL_ handlers */
remove_handlers (node);
/* Remove from tree maybe */
node_fail_or_leave (node);
}
static void
node_fail_or_leave (BtpNode* node)
{
/* FIX: Use "garbage collection" to delete unused nodes. Now that
there are shortcuts, we aren't deleting as agressively as
before. */
/* Delete the node if we're deleting it. */
if (node->is_deleting)
{
BTPP (0, "btp_conn_fail: delete\n");
b_conn_delete (node->conn);
memset (node, 0, sizeof (*node));
g_free (node);
return;
}
BTPP (6, "FAIL: %s:%d\n", STR(node->hostname), node->port);
/* If it's a shortcut, remove it from the shortcut list. Normally,
it will be unrelated. */
if (btp_tree_is_shortcut(node))
{
btp_tree_remove_shortcut (node);
}
/* If it's our child, delete it */
if (btp_tree_is_child(node))
{
BTPP (0, "btp_conn_fail: is_child\n");
btp_tree_remove_child (node);
btp_tree_remove_node (node);
btp_node_delete (node);
return;
}
/* If it's our parent and the root, this is an unrecoverable error.
Do an error upcall. */
else if (btp_tree_is_parent(node) && btp_tree_is_root(node))
{
/* TODO: Try reconnecting a few times */
BTPP (0, "btp_conn_fail: is_parent and root\n");
/* Do an error upcall */
if (TREE->error_func)
{
(TREE->error_func)(TREE, TREE->error_user_data);
return;
}
}
/* If it's our parent and _not_ the root, disconnect from my parent
and connect to the root */
else if (btp_tree_is_parent(node) && !btp_tree_is_root(node))
{
/* Set our parent to root */
TREE->parent = TREE->root;
BTPP (0, "btp_conn_fail: is_parent, not root\n");
/* Connect to the root if unconnected. */
if (b_conn_is_unconnected(TREE->parent->conn))
b_conn_connect(TREE->parent->conn);
/* Otherwise, send a JOIN */
else
{
BPacket* join_packet;
/* Send a join */
join_packet = b_packet_new_join (TREE->parent);
b_conn_send_packet (TREE->parent->conn, join_packet);
BTPP (7, "SEND JOIN %s:%d\n",
TREE->parent->hostname, TREE->parent->port);
/* Schedule a neighbors request. */
schedule_request_neighbors (TREE, TRUE);
}
}
/* If it's the root and not our parent, let it stay down */
else if (btp_tree_is_root(node) && !btp_tree_is_parent(node))
{
/* Do nothing */;
BTPP (0, "btp_conn_fail: is root, not parent\n");
}
/* At this point, the node is neither our root or our parent */
/* If it's our sibling or gparent, delete it. Reset the new_parent
fields if it's also our new_parent. */
else if (btp_tree_is_sibling(node) || btp_tree_is_gparent(node))
{
if (btp_tree_is_sibling(node))
{
btp_tree_remove_sibling (node);
BTPP (0, "btp_conn_fail: is sibling\n");
}
else if (btp_tree_is_gparent(node))
{
g_assert (!btp_tree_is_root(node));
TREE->gparent = NULL;
BTPP (0, "btp_conn_fail: is gparent\n");
}
/* If the node is new_parent, then remove the SWITCH from its
queue and schedule a new parent search. */
if (btp_tree_is_new_parent(node))
{
BTPP (0, "btp_conn_fail: is new parent\n");
TREE->new_parent = NULL;
/* Cancel the SWITCH timeout */
cancel_switch_timeout (TREE);
/* Remove the SWITCH packet from the node's out queue */
b_conn_remove_packets (node->conn, B_PACKET_TYPE_SWITCH);
/* Request neighbors again from parent */
schedule_request_neighbors (TREE, TRUE);
/* (How do we ensure we don't connect to the node again -
maybe we should keep it around?) */
}
btp_tree_remove_node (node);
btp_node_delete (node);
}
/* Otherwise, it's completely unrelated, so delete it. (If it was a
shortcut, we already removed it from the shortcuts list. */
else
{
BTPP (0, "btp_conn_fail: is no one\n");
g_assert (!btp_tree_is_root(node)); /* Sanity check */
btp_tree_remove_node (node);
btp_node_delete (node);
}
}
static void
add_handlers (BtpNode* node)
{
BConn* conn;
g_return_if_fail (node);
g_return_if_fail (node->conn);
g_return_if_fail (TREE);
BTPP (1, "add_handlers\n");
conn = node->conn;
b_conn_handler_add (conn, B_PACKET_TYPE_OK, B_PACKET_OK_SUBTYPE_SWITCH,
receive_ok_switch, node);
b_conn_handler_add (conn, B_PACKET_TYPE_ERROR, B_PACKET_ERROR_SUBTYPE_SWITCH,
receive_error_switch, node);
b_conn_handler_add (conn, B_PACKET_TYPE_UCAST, 0, receive_ucast, node);
b_conn_handler_add (conn, B_PACKET_TYPE_MCAST, 0, receive_mcast, node);
b_conn_handler_add (conn, B_PACKET_TYPE_INFO_REQUEST,
B_PACKET_INFO_SUBTYPE_NEIGHBORS,
receive_request_neighbors, node);
b_conn_handler_add (conn, B_PACKET_TYPE_INFO_REPLY,
B_PACKET_INFO_SUBTYPE_NEIGHBORS,
receive_reply_neighbors, node);
b_conn_handler_add (conn, B_PACKET_TYPE_INFO_REPLY,
B_PACKET_INFO_SUBTYPE_NODE,
receive_reply_node, node);
b_conn_handler_add (conn, B_PACKET_TYPE_JOIN, 0, receive_join, node);
b_conn_handler_add (conn, B_PACKET_TYPE_SWITCH, -1, receive_switch, node);
b_conn_handler_add (conn, B_PACKET_TYPE_LEAVE, 0, receive_leave, node);
b_conn_handler_add (conn, B_PACKET_TYPE_SHORTCUT_ADD, 0, receive_shortcut_add, node);
b_conn_handler_add (conn, B_PACKET_TYPE_OK, B_PACKET_OK_SUBTYPE_SHORTCUT,
receive_ok_shortcut, node);
b_conn_handler_add (conn, B_PACKET_TYPE_ERROR, B_PACKET_ERROR_SUBTYPE_SHORTCUT,
receive_error_shortcut, node);
b_conn_handler_add (conn, B_PACKET_TYPE_SHORTCUT_REMOVE, 0, receive_shortcut_remove, node);
/* Start handling any packet if there's a packet func */
if (TREE->packet_func)
b_conn_handler_add (conn, -1, -1, receive_any, node);
}
static void
remove_handlers (BtpNode* node)
{
BConn* conn;
g_return_if_fail (node);
g_return_if_fail (node->conn);
BTPP (1, "remove_handlers\n");
conn = node->conn;
b_conn_handler_remove (conn, B_PACKET_TYPE_OK, B_PACKET_OK_SUBTYPE_SWITCH, node);
b_conn_handler_remove (conn, B_PACKET_TYPE_ERROR, B_PACKET_ERROR_SUBTYPE_SWITCH, node);
b_conn_handler_remove (conn, B_PACKET_TYPE_INFO_REQUEST,
B_PACKET_INFO_SUBTYPE_NEIGHBORS, node);
b_conn_handler_remove (conn, B_PACKET_TYPE_INFO_REPLY,
B_PACKET_INFO_SUBTYPE_NEIGHBORS, node);
b_conn_handler_remove (conn, B_PACKET_TYPE_JOIN, 0, node);
b_conn_handler_remove (conn, B_PACKET_TYPE_SWITCH, -1, node);
b_conn_handler_remove (conn, B_PACKET_TYPE_LEAVE, 0, node);
/* Stop handling any packet if there's a packet func. */
if (TREE && TREE->packet_func)
b_conn_handler_remove (conn, -1, -1, node);
}
/* ************************************************************ */
static void
receive_any (BConn* conn, BPacket* packet, gpointer user_data)
{
BtpNode* node = (BtpNode*) user_data;
g_return_if_fail (packet);
g_return_if_fail (node);
g_return_if_fail (TREE);
BTPP (1, "receive_any\n");
if (TREE->packet_func)
TREE->packet_func (TREE, node, packet, TREE->packet_user_data);
}
static void
receive_ok_switch (BConn* conn, BPacket* packet, gpointer user_data)
{
BtpNode* node = (BtpNode*) user_data;
BtpNode* parent;
BtpNode* gparent;
BPacket* new_packet;
g_return_if_fail (node);
g_return_if_fail (packet);
g_return_if_fail (packet->type == B_PACKET_TYPE_OK);
g_return_if_fail (packet->subtype == B_PACKET_OK_SUBTYPE_SWITCH);
g_return_if_fail (TREE);
BTPP (1, "receive_ok_switch\n");
BTPP (7, "RECV OK-SWITCH %s:%d\n", node->hostname, node->port);
++TREE->num_ok;
/* ******************** */
/* Checks */
/* We should have a new parent. It's possible that we btp_fail'ed
the node and it recovered and sent us this OK. */
if (TREE->new_parent == NULL)
return;
/* This node should be our new parent */
if (TREE->new_parent != node)
return;
/* Cancel the switch timeout */
cancel_switch_timeout (TREE);
/* Don't want to switch to my current parent (Sanity check) */
if (btp_tree_is_parent(node))
{
g_warning ("Attempt to switch parents to current parent\n");
return;
}
/* This node should be my sibling or grandparent. (Sanity check -
this should be correct internally.) */
if (!btp_tree_is_sibling (node) && !btp_tree_is_gparent (node))
{
g_warning ("Received OK from odd relation\n");
return;
}
/* ******************** */
/* Action */
/* Send a LEAVE to my old parent. The parent will probably
close the connection once it receives the LEAVE. */
new_packet = b_packet_new_leave (TREE->parent);
b_conn_send_packet (TREE->parent->conn, new_packet);
BTPP (7, "SEND LEAVE %s:%d\n", TREE->parent->hostname, TREE->parent->port);
/* Switch */
parent = TREE->parent;
TREE->parent = TREE->new_parent;
TREE->new_parent = NULL;
gparent = TREE->gparent;
TREE->gparent = NULL;
btp_tree_remove_sibling (TREE->parent);
/* Send node info since the topology changed */
send_node_info (TREE);
/* Disconnect from old parent (if it isn't a shortcut) */
if ( !btp_tree_is_shortcut(parent) )
{
if ( b_conn_is_connected(parent->conn) )
b_conn_close (parent->conn);
}
/* Disconnect from old gparent (unless now parent or shortcut) */
if ( gparent && !(btp_tree_is_parent(gparent) || btp_tree_is_shortcut(gparent)) )
{
if ( b_conn_is_connected(gparent->conn) )
b_conn_close (gparent->conn);
}
/* Disconnect from old siblings */
while (TREE->siblings)
{
BtpNode* sibling = (BtpNode*) TREE->siblings->data;
g_return_if_fail (TREE->me != sibling);
g_return_if_fail (TREE->parent != sibling);
TREE->siblings = g_slist_remove_link (TREE->siblings, TREE->siblings);
if ( b_conn_is_connected(conn) && !btp_tree_is_shortcut(sibling) )
b_conn_close (sibling->conn);
}
/* Get a new list of neighbors */
schedule_request_neighbors (TREE, FALSE);
}
static void
receive_error_switch (BConn* conn, BPacket* packet, gpointer user_data)
{
BtpNode* node = (BtpNode*) user_data;
BAddress* follow_addr;
g_return_if_fail (node);
g_return_if_fail (packet);
g_return_if_fail (packet->type == B_PACKET_TYPE_ERROR);
g_return_if_fail (packet->subtype == B_PACKET_ERROR_SUBTYPE_SWITCH);
g_return_if_fail (TREE);
BTPP (1, "receive_error_switch\n");
++TREE->num_error;
/* Cancel the switch timeout */
cancel_switch_timeout (TREE);
/* ******************** */
/* Checks */
/* We should have a new parent. It's possible that we
btp_fail'ed the node and it recovered and sent us this OK. */
if (TREE->new_parent == NULL)
{
g_warning ("Received weird switch ERROR (I have no new parent)\n");
return;
}
/* ******************** */
/* Action */
/* If in follow mode, get node's new parent. If we are one hop from
this node, set its follow flag. */
if (TREE->follow_nodes && packet->data &&
!b_packet_parse_addr(packet, &follow_addr))
{
BtpNode* follow_node;
/* Find node */
follow_node = btp_tree_find_node (TREE, follow_addr->hostname,
follow_addr->port);
/* Mark it if sibling or gparent */
if (follow_node &&
(btp_tree_is_gparent(follow_node) ||
btp_tree_is_sibling(follow_node)) &&
TREE->new_parent->conn)
{
follow_node->follow = TRUE;
follow_node->follow_distance = TREE->new_parent->conn->distance;
}
b_address_delete (follow_addr);
}
/* Reset new_parent. */
TREE->new_parent = NULL;
/* Request neighbors again. Presumably we acted on bad information.
This will start the new parent search process again. */
schedule_request_neighbors (TREE, TRUE);
}
static void
receive_ucast (BConn* conn, BPacket* packet, gpointer user_data)
{
BtpNode* node = (BtpNode*) user_data;
g_return_if_fail (node);
g_return_if_fail (packet);
g_return_if_fail (packet->type == B_PACKET_TYPE_UCAST);
g_return_if_fail (TREE);
BTPP (1, "receive_ucast\n");
if (TREE->ucast_read_func)
{
TREE->ucast_read_func (TREE, node, packet->data, g_ntohs(packet->length),
TREE->ucast_read_user_data);
}
}
static void
receive_mcast (BConn* conn, BPacket* pkt, gpointer user_data)
{
BtpNode* node = (BtpNode*) user_data;
g_return_if_fail (node);
g_return_if_fail (pkt);
g_return_if_fail (pkt->type == B_PACKET_TYPE_MCAST);
g_return_if_fail (TREE);
BTPP (1, "receive_mcast\n");
/* Drop if it's a duplicate */
if (seq_num_check(node, pkt))
{
BTPP (14, "SEQ: Received duplicate mcast packet\n");
return;
}
/* Warn if not from neighbor */
if (!btp_tree_is_mesh_neighbor(node))
{
g_warning ("Received multicast packet from non-neighbor: %s:%d\n",
node->hostname, node->port);
return;
}
/* Pass up */
if (TREE->mcast_read_func)
{
TREE->mcast_read_func (TREE, node, pkt->data, g_ntohs(pkt->length),
TREE->mcast_read_user_data);
}
/* Forward to neighbors */
btp_tree_forward_mcast (TREE, node, pkt);
}
static void
receive_request_neighbors (BConn* conn, BPacket* packet, gpointer user_data)
{
BtpNode* node = (BtpNode*) user_data;
BPacket* new_packet;
g_return_if_fail (node);
g_return_if_fail (packet);
g_return_if_fail (packet->type == B_PACKET_TYPE_INFO_REQUEST);
g_return_if_fail (packet->subtype == B_PACKET_INFO_SUBTYPE_NEIGHBORS);
g_return_if_fail (TREE);
BTPP (1, "receive_request_neighbors\n");
new_packet = b_packet_new_info_reply_neighbors (node, TREE->parent, TREE->children);
b_conn_send_packet (node->conn, new_packet);
BTPP (7, "SEND INFOREP-NEIGHBORS %s:%d\n", node->hostname, node->port);
}
static void
receive_reply_neighbors (BConn* conn, BPacket* packet, gpointer user_data)
{
BtpNode* node = (BtpNode*) user_data;
BAddress* parent;
GSList* children;
GSList* i;
g_return_if_fail (node);
g_return_if_fail (packet);
g_return_if_fail (packet->type == B_PACKET_TYPE_INFO_REPLY);
g_return_if_fail (packet->subtype == B_PACKET_INFO_SUBTYPE_NEIGHBORS);
g_return_if_fail (TREE);
BTPP (1, "receive_reply_neighbors\n");
/* Ignore if from a node that isn't my parent or if I'm passive */
if (node != TREE->parent || TREE->passive)
return;
/* Read the neighbors addresses */
if (b_packet_parse_info_reply_neighbors (packet, &parent, &children))
{
g_warning ("Received bad neighbors reply\n");
b_address_delete (parent);
b_addresses_delete (children);
schedule_request_neighbors (TREE, FALSE);
return;
}
/* Save gparent */
TREE->gparent = NULL;
if (parent && parent->port)
{
BtpNode* gparent;
BTPP (7, "RECV INFOREP-NEIGHBORS %s:%d (GPARENT)\n",
parent->hostname, parent->port);
gparent = btp_tree_find_node (TREE, parent->hostname, parent->port);
if (gparent == NULL)
gparent = btp_node_new (TREE, parent->hostname, parent->port, NULL);
TREE->gparent = gparent;
}
b_address_delete (parent);
/* Save siblings */
g_slist_free (TREE->siblings);
TREE->siblings = NULL;
for (i = children; i != NULL; i = i->next)
{
BtpNode* sibling;
BAddress* addr;
/* Get the next address */
addr = (BAddress*) i->data;
/* Ignore if port is 0 */
if (addr->port == 0)
{
g_warning ("Received child with port of 0\n");
continue;
}
BTPP (7, "RECV INFOREP-NEIGHBORS %s:%d (SIBLING)\n",
addr->hostname, addr->port);
/* Check if I already have this node */
sibling = btp_tree_find_node (TREE, addr->hostname, addr->port);
if (sibling == NULL)
{
sibling = btp_node_new (TREE, addr->hostname, addr->port, NULL);
btp_tree_add_sibling (sibling);
}
/* Add sibling to sibling list, if not already there. Don't add
if it's me, a parent, sibling, or child. */
else if (!btp_tree_is_sibling(sibling) &&
sibling != TREE->me &&
!btp_tree_is_parent(sibling) &&
!btp_tree_is_child(sibling))
{
btp_tree_add_sibling (sibling);
}
}
b_addresses_delete (children);
/* Connect to all relations to get the ping distance */
for (i = TREE->siblings; i != NULL; i = i->next)
{
BtpNode* sibling = (BtpNode*) i->data;
b_conn_connect (sibling->conn);
}
if (TREE->gparent)
b_conn_connect (TREE->gparent->conn);
/* Close connection more than two hops away. This will result in an
upcall to btp_conn_close then btp_conn_fail and the node will be
deleted. The upcall may occur immediately. */
for (i = TREE->nodes; i != NULL; )
{
BtpNode* n = (BtpNode*) i->data;
i = i->next;
if (!btp_tree_is_me(n) && !btp_tree_is_one_hop(n) && !btp_tree_is_two_hop(n))
b_conn_close (n->conn);
}
/* Set a timer to later find a new parent based on ping times */
schedule_find_new_parent (TREE);
}
static void
receive_join (BConn* conn, BPacket* packet, gpointer user_data)
{
BtpNode* node = (BtpNode*) user_data;
g_return_if_fail (node);
g_return_if_fail (packet);
g_return_if_fail (packet->type == B_PACKET_TYPE_JOIN);
g_return_if_fail (TREE);
BTPP (1, "receive_join\n");
BTPP (7, "RECV JOIN %s:%d\n", node->hostname, node->port);
++TREE->num_join;
/* ******************** */
/* Checks */
g_return_if_fail (!TREE->passive); /* Don't allow a JOIN if passive. */
g_return_if_fail (!btp_tree_is_me(node)); /* Don't join myself. */
g_return_if_fail (!btp_tree_is_root(node)); /* Don't allow root to join. */
/* ******************** */
/* Action */
/* If the node is already a child, 'ignore' the JOIN. This
might happen if the child resets and rejoins. */
if (btp_tree_is_child(node))
return;
/* If the node is my parent, ignore it. In practice, this
shouldn't happen. It could happen if the parent resets, is
confused, and rejoins. However, by the time this happen, I
should have a new parent. */
if (btp_tree_is_parent(node))
return;
/* Remove it from the sibling list. This could happen if the
node resets then sends us a JOIN for some reason. */
if (btp_tree_is_sibling (node))
btp_tree_remove_sibling (node);
/* Add the node to my list of children */
btp_tree_add_child (node);
}
static void
receive_switch (BConn* conn, BPacket* pkt, gpointer user_data)
{
BtpNode* node = (BtpNode*) user_data;
BAddress* parent = NULL;
gboolean switch_ok = FALSE;
g_return_if_fail (node);
g_return_if_fail (pkt);
g_return_if_fail (pkt->type == B_PACKET_TYPE_SWITCH);
g_return_if_fail (TREE);
BTPP (1, "receive_switch\n");
++TREE->num_switch;
/* ******************** */
/* Checks */
g_return_if_fail (!TREE->passive); /* Don't allow a SWITCH if passive */
g_return_if_fail (!btp_tree_is_me(node)); /* Don't switch to myself */
g_return_if_fail (!btp_tree_is_parent(node)); /* Don't allow parent to switch */
g_return_if_fail (!btp_tree_is_root(node)); /* Don't allow root to switch */
/* ******************** */
/* Action */
BTPP (7, "RECV SWITCH %s:%d\n", node->hostname, node->port);
/* If the node is already my child, send an OK. */
if (btp_tree_is_child(node))
{
switch_ok = TRUE;
goto switch_done;
}
/* Can't switch if I'm also trying to switch. */
if (TREE->new_parent != NULL)
{
BTPP (7, "RECV SWITCH ALREADY SWITCHING\n");
goto switch_done;
}
/* Read the parent address. This is the switching node's parent. */
if (b_packet_parse_switch(pkt, &parent))
{
g_warning ("Received bad switch\n");
return;
}
/* Check relations */
if (pkt->subtype == B_PACKET_SWITCH_SUBTYPE_SIBLING)
{
/* Sibling switches: Can't switch if we have different parents.
Otherwise, this might cause a loop. */
if (parent->port != TREE->parent->port ||
strcmp(parent->hostname, TREE->parent->hostname) != 0)
{
BTPP (7, "RECV SWITCH SIBLING: ERROR: PARENT MISMATCH\n");
goto switch_done;
}
/* Ok: Remove from sibling list */
btp_tree_remove_sibling (node);
BTPP (7, "RECV SWITCH SIBLING: OK\n");
}
else if (pkt->subtype == B_PACKET_SWITCH_SUBTYPE_GPARENT)
{
BtpNode* kid_node;
/* Grandparent switches: Can't switch unless node's parent is my
child. Otherwise, this might cause a loop. */
kid_node = btp_tree_find_node (TREE, parent->hostname, parent->port);
if (!kid_node || !btp_tree_is_child (kid_node))
{
BTPP (7, "RECV SWITCH GPARENT: ERROR: PARENT MISMATCH %s:%d\n",
parent->hostname, parent->port);
goto switch_done;
}
BTPP (7, "RECV SWITCH GPARENT: OK\n");
}
else
goto switch_done;
/* Ok to switch. Add to my children list. */
btp_tree_add_child (node);
switch_ok = TRUE;
/* Send node info since the topology changed */
send_node_info (TREE);
switch_done:
b_address_delete (parent);
/* Send an OK or error message */
if (switch_ok)
{
BPacket* ok_pkt;
ok_pkt = b_packet_new_ok (node->conn, B_PACKET_OK_SUBTYPE_SWITCH);
b_conn_send_packet (node->conn, ok_pkt);
BTPP (7, "SEND OK-SWITCH %s:%d\n", node->hostname, node->port);
}
else
{
BtpNode* nparent = NULL;
guint slen = 0;
guint len = 0;
BPacket* error_pkt;
++TREE->num_switch_bad;
if (TREE->new_parent)
nparent = TREE->new_parent;
else if (TREE->parent)
nparent = TREE->parent;
if (nparent)
{
slen = strlen (nparent->hostname);
len = slen + 3;
}
error_pkt = b_packet_new (node->conn, B_PACKET_TYPE_ERROR, len);
error_pkt->subtype = B_PACKET_ERROR_SUBTYPE_SWITCH;
if (nparent)
{
memcpy (error_pkt->data, nparent->hostname, slen);
error_pkt->data[slen + 0] = '\0';
error_pkt->data[slen + 1] = (nparent->port & 0xFF00) >> 8;
error_pkt->data[slen + 2] = nparent->port & 0x00FF;
}
b_conn_send_packet (node->conn, error_pkt);
BTPP (7, "SEND ERROR-SWITCH %s:%d\n", node->hostname, node->port);
}
}
static void
receive_leave (BConn* conn, BPacket* packet, gpointer user_data)
{
BtpNode* node = (BtpNode*) user_data;
g_return_if_fail (node);
g_return_if_fail (packet);
g_return_if_fail (packet->type == B_PACKET_TYPE_LEAVE);
g_return_if_fail (TREE);
g_return_if_fail (node != TREE->me);
BTPP (1, "receive_leave\n");
BTPP (7, "RECV LEAVE %s:%d\n", node->hostname, node->port);
/* Keep the handlers */
/* Remove from tree */
node_fail_or_leave (node);
/* Send node info since the topology changed */
send_node_info (TREE);
}
/* ************************************************************ */
static void
schedule_request_neighbors (BtpTree* tree, gboolean soon)
{
guint time;
guint range;
g_return_if_fail (tree);
BTPP (1, "schedule_request_neighbors\n");
if (tree->request_neighbors_timeout != 0)
return;
if (soon)
{
time = REQUEST_NEIGHBORS_TIME;
range = REQUEST_NEIGHBORS_RANGE;
}
else
{
time = NEXT_REQUEST_NEIGHBORS_TIME;
range = NEXT_REQUEST_NEIGHBORS_RANGE;
}
rand_timer_set (&tree->request_neighbors_timeout, time, range,
request_neighbors_cb, tree);
}
static void
cancel_request_neighbors (BtpTree* tree)
{
g_return_if_fail (tree);
BTPP (1, "cancel_request_neighbor\n");
if (tree->request_neighbors_timeout)
{
g_source_remove(tree->request_neighbors_timeout);
tree->request_neighbors_timeout = 0;
}
}
static gboolean
request_neighbors_cb (gpointer data)
{
BtpTree* tree = (BtpTree*) data;
BPacket* packet;
BTPP (1, "request_neighbors_cb\n");
g_return_val_if_fail (tree, FALSE);
g_return_val_if_fail (tree->parent, FALSE);
tree->request_neighbors_timeout = 0;
packet = b_packet_new_info_request_neighbors (tree->parent);
b_conn_send_packet (tree->parent->conn, packet);
BTPP (7, "SEND INFOREQ-NEIGHBORS %s:%d\n", tree->parent->hostname, tree->parent->port);
return FALSE;
}
/* ************************************************************ */
static void
schedule_find_new_parent (BtpTree* tree)
{
g_return_if_fail (tree);
BTPP (1, "schedule_find_new_parent\n");
rand_timer_set (&tree->find_new_parent_timeout,
FIND_NEW_PARENT_TIME, FIND_NEW_PARENT_RANGE,
find_new_parent_cb, tree);
}
static gboolean
find_new_parent_cb (gpointer data)
{
BtpTree* tree = (BtpTree*) data;
BtpNode* new_parent;
BTPP (1, "find_new_parent_cb\n");
BTPP (7, "FIND NEW PARENT\n");
g_return_val_if_fail (tree, FALSE);
/* I should not be root and should have a parent. TODO: Is is
possible that we can reach this point and not have a parent? */
g_return_val_if_fail (tree->root != tree->me, FALSE);
g_return_val_if_fail (tree->parent != NULL, FALSE);
/* We should be in switching mode */
g_return_val_if_fail (tree->find_new_parent_timeout != 0, FALSE);
tree->find_new_parent_timeout = 0;
/* We should not have a switching candidate or be in the process of
switching. */
g_return_val_if_fail (tree->new_parent == NULL, FALSE);
g_return_val_if_fail (tree->switch_timeout == 0, FALSE);
/* Figure out who the new parent should be */
new_parent = find_new_parent (tree);
/* Switch if we found a new parent */
if (new_parent)
{
BPacket* switch_packet;
guint8 subtype;
BTPP (1, "find_new_parent_cb: Switching parent\n");
/* Cancel any request neighbor timeout */
cancel_request_neighbors (tree);
tree->new_parent = new_parent;
/* We will remove the parent from the list of siblings in the
OK/ERROR code. */
if (tree->gparent == new_parent)
{
subtype = B_PACKET_SWITCH_SUBTYPE_GPARENT;
BTPP (7, "SEND SWITCH GPARENT ");
}
else
{
subtype = B_PACKET_SWITCH_SUBTYPE_SIBLING;
BTPP (7, "SEND SWITCH SIBLING ");
}
BTPP (7, "%s:%d (%d)\n", new_parent->hostname, new_parent->port, new_parent->conn->distance);
switch_packet = b_packet_new_switch (new_parent, tree->parent, subtype);
b_conn_send_packet (new_parent->conn, switch_packet);
schedule_switch_timeout (tree);
}
else
{
BTPP (0, "find_new_parent_cb: Did not find a better parent\n");
/* Wait a while, request neighbors, and try again. */
schedule_request_neighbors(tree, FALSE);
}
BTPP (0, "find_new_parent_cb DONE\n");
return FALSE;
}
static BtpNode*
find_new_parent (BtpTree* tree)
{
BtpNode* parent;
BtpNode* gparent;
BtpNode* closest;
BtpNode* follow;
guint distance;
GSList* si;
g_return_val_if_fail (tree, NULL);
g_return_val_if_fail (tree->parent, NULL);
BTPP (1, "find_new_parent\n");
parent = tree->parent;
gparent = tree->gparent;
/* Closest is our parent (unless we don't know the distance) */
if (parent->conn->distance != 0)
{
closest = parent;
distance = parent->conn->distance;
}
else
{
closest = NULL;
distance = G_MAXUINT;
}
/* Find the closest sibling */
for (si = tree->siblings; si != NULL; si = si->next)
{
BtpNode* sibling = (BtpNode*) si->data;
/* Skip siblings that we don't have a distance for or are known
bad parents. */
if (sibling->conn->distance == 0 || sibling->is_bad_parent)
continue;
/* If the sibling is closer, then save it */
if (sibling->conn->distance <= distance)
{
BTPP (10, "FIND: TRY SIBLING %d\n", sibling->conn->distance);
closest = sibling;
distance = sibling->conn->distance;
}
}
/* Check grandparent */
if (gparent && !(gparent->conn->distance == 0 || gparent->is_bad_parent) &&
gparent->conn->distance <= distance)
{
BTPP (10, "FIND: TRY GPARENT %d\n", gparent->conn->distance);
closest = gparent;
distance = gparent->conn->distance;
}
/* Check if a previous best-potential-parent would make a good
parent. find_follow_node returns the node that node switched
to. */
follow = find_follow_node (tree);
if (follow)
{
/* Switch if it's closer than the current closest OR there is
not current closest. We can always switch back. */
if ((closest && distance > follow->follow_distance) || !closest)
{
BTPP (10, "FIND: TRY FOLLOW %d\n", follow->follow_distance);
closest = follow;
distance = follow->follow_distance;
}
/* Clear follow flags. We only attempt to use the follow node
once. Either we use it or we find something better. */
follow->follow = FALSE;
follow->follow_distance = 0;
}
/* Return NULL if we didn't find one or the best one is our parent */
if (closest == NULL || closest == parent)
{
BTPP (10, "FIND: CLOSEST <NONE>\n");
return NULL;
}
BTPP (10, "FIND: CLOSEST %s:%d (%d)\n", closest->hostname, closest->port, distance);
/* Check if aggressively switching (for debugging purposes) */
if (btp_debug_flags & (1 << 20))
{
BTPP (20, "FIND: AGGRESSIVE SWITCH\n");
return closest;
}
/* Heuristic: If the closest is a sibling, less than 10 ms away, and
the parent has some children, then definately switch to it. */
#if 0
if (btp_tree_is_sibling (closest) &&
closest->conn->distance <= 10 &&
btp_tree_parent_degree (tree) > (tree->max_degree - 2))
return closest;
#endif
/* Otherwise, only switch if it's better than 20% closer _or_ the
parent has too large a degree. This means that a node won't
switch if a sibling is about as close as the parent _and_ the
parent doesn't have many children. */
if (((double) closest->conn->distance <=
(.80 * (double) parent->conn->distance)) ||
(btp_tree_parent_degree (tree) > tree->max_degree))
return closest;
return NULL;
}
static BtpNode*
find_follow_node (BtpTree* tree)
{
GSList* i;
g_return_val_if_fail (tree, NULL);
if (!tree->follow_nodes)
return NULL;
if (tree->parent && tree->parent->follow)
return tree->parent;
if (tree->gparent && tree->gparent->follow)
return tree->gparent;
for (i = tree->siblings; i != NULL; i = i->next)
{
BtpNode* sibling = (BtpNode*) i->data;
if (sibling->follow)
return sibling;
}
return NULL;
}
/* ************************************************************ */
static void
schedule_switch_timeout (BtpTree* tree)
{
g_return_if_fail (tree != NULL);
BTPP (1, "schedule_switch_timeout\n");
rand_timer_set (&tree->switch_timeout,
SWITCH_TIMEOUT_TIME, SWITCH_TIMEOUT_RANGE,
switch_timeout_cb, tree);
}
static void
cancel_switch_timeout (BtpTree* tree)
{
g_return_if_fail (tree != NULL);
BTPP (1, "cancel_schedule_switch_timeout\n");
rand_timer_cancel (&tree->switch_timeout);
}
static gboolean
switch_timeout_cb (gpointer data)
{
BtpTree* tree = (BtpTree*) data;
g_return_val_if_fail (tree->new_parent, FALSE);
g_return_val_if_fail (tree->switch_timeout != 0, FALSE);
BTPP (1, "switch_timeout_cb\n");
BTPP (7, "SWITCH TIMEOUT %s:%d\n", tree->new_parent->hostname, tree->new_parent->port);
/* Mark the node as a bad parent */
tree->new_parent->is_bad_parent = TRUE;
/* Remove any switches that we might be about to send */
b_conn_remove_packets (tree->new_parent->conn, B_PACKET_TYPE_SWITCH);
/* Reset the new parent search */
tree->new_parent = 0;
tree->switch_timeout = 0;
/* Request neighbors and start again */
schedule_request_neighbors (tree, TRUE);
return FALSE;
}
/* ************************************************************ */
/* Sequence number */
#define SQ_ID 0
#define SQ_SEQ 1
#define SQ_TIME 2
#define SQ_MAX_DIFF 1000 /* Maximum difference in seq num. If exceeded,
we jump to the new seq number. */
/* Check to see if this packet is likely to be a duplicate. If it's
a duplicate, return TRUE. */
static gboolean
seq_num_check (BtpNode* node, BPacket* packet)
{
guint id;
guint seq;
guint i;
guint least_index = 0;
guint least_time = G_MAXUINT;
guint last_seq;
id = g_ntohl (packet->source_id);
seq = g_ntohs (packet->seq);
BTPP (14, "SEQ: Check %d %d from %s:%d\n",
id, seq, node->hostname, node->port);
/* Check if it's my sequence number */
if (id == TREE->group.source_id)
{
guint last_seq = TREE->group.seq_num;
BTPP (14, "SEQ: Source ID is my ID (%u), check if actually mine\n",
TREE->group.source_id);
/* If it's within range of recently sent packets, it's probably
my packet and a duplicate. */
if ( seq == last_seq ||
((seq > last_seq) && (seq - last_seq < SQ_MAX_DIFF)) ||
((seq < last_seq) && (seq + (G_MAXUINT16 - last_seq) < SQ_MAX_DIFF)) ||
((seq < last_seq) && (last_seq - seq < SQ_MAX_DIFF)) ||
((seq > last_seq) && (last_seq + (G_MAXUINT16 - last_seq) < SQ_MAX_DIFF)) )
{
BTPP (14, "SEQ: Ok, received my packet\n");
return TRUE;
}
/* Otherwise, it's probably a collision. Change my source ID */
else
{
guint new_source_id;
new_source_id = rand() % G_MAXUINT32;
g_warning ("SEQ: Source ID collision. Changing from %u to %u\n",
TREE->group.source_id, new_source_id);
TREE->group.source_id = new_source_id;
return FALSE;
}
}
/* Find index in cache */
for (i = 0; i < SEQ_CACHE_LEN && TREE->seq_cache[i][SQ_ID]; ++i)
{
/* Break if we found an entry for this id */
if (TREE->seq_cache[i][SQ_ID] == id)
break;
/* Note the oldest index */
if (TREE->seq_cache[i][SQ_TIME] < least_time)
least_index = i;
}
/* If not in cache, add. We assume it is not a duplicate. */
if (i == SEQ_CACHE_LEN || TREE->seq_cache[i][SQ_ID] == 0)
{
BTPP (14, "SEQ: %d not in cache, adding\n", id);
if (i != SEQ_CACHE_LEN)
least_index = i;
TREE->seq_cache[least_index][SQ_ID] = g_ntohl(packet->source_id);
TREE->seq_cache[least_index][SQ_SEQ] = g_ntohs(packet->seq);
TREE->seq_cache[least_index][SQ_TIME] = millitime();
return FALSE;
}
/* Note access time */
TREE->seq_cache[i][SQ_TIME] = millitime();
last_seq = TREE->seq_cache[i][SQ_SEQ];
/* If the sequence number is slightly larger, it is a new packet */
if ( ((seq > last_seq) && (seq - last_seq < SQ_MAX_DIFF)) ||
((seq < last_seq) && (seq + (G_MAXUINT16 - last_seq) < SQ_MAX_DIFF)) )
{
BTPP (14, "SEQ: next in sequence, ok\n");
TREE->seq_cache[i][SQ_SEQ] = seq;
return FALSE;
}
/* If the sequence number is slightly smaller, it is a duplicate packet */
else if ( seq == last_seq ||
((seq < last_seq) && (last_seq - seq < SQ_MAX_DIFF)) ||
((seq > last_seq) && (last_seq + (G_MAXUINT16 - last_seq) < SQ_MAX_DIFF)) )
{
BTPP (14, "SEQ: prev in sequence, duplicate\n");
return TRUE;
}
/* Otherwise, the difference is great. Assume it is not a duplicate
packet and reset the sequence number. */
else
{
BTPP (14, "SEQ: jump in sequence number\n");
g_warning ("Huge sequence number jump: %u to %u\n", last_seq, seq);
TREE->seq_cache[i][SQ_SEQ] = seq;
return FALSE;
}
return FALSE;
}
/* ************************************************************ */
/* Shortcuts */
static void
schedule_find_new_shortcut_timeout (BtpTree* tree)
{
g_return_if_fail (tree);
BTPP (1, "schedule_find_new_shortcut_timeout\n");
/* FIX: We probably want to delay this until we switch a bit. */
/* Don't bother if we aren't using shortcuts */
if (!tree->use_shortcuts)
return;
rand_timer_set (&tree->find_new_shortcut_timeout,
FIND_NEW_SHORTCUT_TIME, FIND_NEW_SHORTCUT_RANGE,
find_new_shortcut_cb, tree);
}
static gboolean
find_new_shortcut_cb (gpointer data)
{
BtpTree* tree = (BtpTree*) data;
guint degree;
g_return_val_if_fail (tree, FALSE);
BTPP (1, "find_new_shortcut_cb\n");
/* Find new short cut only if we have room */
degree = btp_tree_degree (tree);
if (degree < tree->max_degree)
find_new_shortcut (tree);
/* reschedule? */
/* Yes, we want more find_new_shortcut_cb callbacks */
return TRUE;
}
static void
find_new_shortcut (BtpTree* tree)
{
guint degree;
GSList* i;
GSList* potential_shortcuts = NULL;
guint num_potential_shortcuts = 0;
guint num_shortcut;
BtpNode* snode; /* shortcut node */
g_return_if_fail (tree);
BTPP (12, "SC: Find new shortcut\n");
/* Ignore if we have too many neighbors */
degree = btp_tree_degree (tree);
if (degree >= tree->max_degree)
return;
/* Build list of potential shortcuts */
for (i = tree->nodes; i != NULL; i = i->next)
{
BtpNode* node = (BtpNode*) i->data;
/* Exclude me, neighbors, current shortcuts, the new parent */
if ( btp_tree_is_me(node) ||
btp_tree_is_parent(node) ||
btp_tree_is_child(node) ||
btp_tree_is_shortcut(node) ||
btp_tree_is_new_parent(node) )
continue;
/* Ignore if we are currently adding a shortcut */
if ( node->shortcut_ping_timeout || node->shortcut_add_timeout )
continue;
/* Ignore if we don't know overlay distance */
if ( !node->overlay_distance )
continue;
BTPP (12, "SC: Potential SC: %s:%d\n", node->hostname, node->port);
/* Add it to the list */
potential_shortcuts = g_slist_prepend (potential_shortcuts, node);
num_potential_shortcuts++;
}
/* Ignore if no potential shortcuts */
if (num_potential_shortcuts == 0)
return;
/* Pick a shortcut at random */
num_shortcut = rand() % num_potential_shortcuts;
BTPP (12, "SC: Randomly choose shortcut %d of %d\n", num_shortcut, num_potential_shortcuts);
snode = (BtpNode*) g_slist_nth (potential_shortcuts, num_shortcut)->data;
g_slist_free (potential_shortcuts);
BTPP (12, "SC: Choose shortcut: %s:%d\n", snode->hostname, snode->port);
/* If we don't know the network distance, connect, ping, and set timer */
if (!snode->conn->distance)
{
BTPP (12, "SC: Connecting...\n");
/* Connect. A ping will be sent shortly. */
if (b_conn_is_unconnected(snode->conn))
b_conn_connect (snode->conn);
/* Send a ping immediately */
else
b_conn_ping_send (snode->conn);
/* Check node again soon */
rand_timer_set (&snode->shortcut_ping_timeout,
SHORTCUT_PING_TIMEOUT_TIME, SHORTCUT_PING_TIMEOUT_RANGE,
shortcut_ping_timeout_cb, snode);
}
/* Otherwise, we can calculate the RDP */
else if (is_good_shortcut(snode))
{
BTPP (12, "SC: Adding shortcut...\n");
add_shortcut (tree, snode);
}
/* Otherwise, it's not a good shortcut */
}
static gboolean
shortcut_ping_timeout_cb (gpointer data)
{
BtpNode* node = (BtpNode*) data;
BTPP (12, "SC: Shortcut ping timeout to %s:%d\n", node->hostname, node->port);
node->shortcut_ping_timeout = 0;
/* If we know the distance */
if (node->conn->distance && is_good_shortcut(node))
{
BTPP (12, "SC: Adding shortcut...\n");
add_shortcut (TREE, node);
}
return FALSE;
}
static gboolean
is_good_shortcut (BtpNode* node)
{
double rdp;
/* Assume it's bad if we don't know the distance */
if ( !node->overlay_distance || !node->conn->distance )
return FALSE;
/* Calculate RDP */
rdp = (double) node->overlay_distance / (double) node->conn->distance;
BTPP (12, "SC: RDP to %s:%d is %f (%d / %d)\n",
node->hostname, node->port, rdp,
node->overlay_distance, node->conn->distance);
/* If the RDP is above the threshhold, it's good */
if (rdp >= SHORTCUT_RDP_THRESHHOLD)
return TRUE;
return FALSE;
}
static void
add_shortcut (BtpTree* tree, BtpNode* node)
{
BPacket* pkt;
g_return_if_fail (tree);
g_return_if_fail (node);
g_return_if_fail (!node->shortcut_add_timeout);
g_return_if_fail (!node->shortcut_ping_timeout);
BTPP (12, "SC: Add shortcut to %s:%d\n", node->hostname, node->port);
/* Send packet */
pkt = b_packet_new (node->conn, B_PACKET_TYPE_SHORTCUT_ADD, 0);
b_conn_send_packet (node->conn, pkt);
/* Set shortcut-add timer */
rand_timer_set (&node->shortcut_add_timeout,
SHORTCUT_ADD_TIMEOUT_TIME, SHORTCUT_ADD_TIMEOUT_RANGE,
shortcut_add_timeout_cb, node);
}
static void
receive_shortcut_add (BConn* conn, BPacket* packet, gpointer user_data)
{
BtpNode* node = (BtpNode*) user_data;
guint degree;
BPacket* pkt;
/* Reject if a neighbor or new parent */
if ( btp_tree_is_parent(node) || btp_tree_is_child(node) ||
btp_tree_is_new_parent(node) )
goto send_error;
/* Ok if already a shortcut */
if ( btp_tree_is_shortcut(node) )
goto send_ok;
/* Reject if degree is at or above maximum */
degree = btp_tree_degree(TREE);
if ( degree >= TREE->max_degree )
goto send_error;
/* Note it's ok if me and this node are simultaneously adding
shortcuts to each other */
/* Add to shortcut list */
btp_tree_add_shortcut(node);
/* Send ok */
send_ok:
pkt = b_packet_new_ok (node->conn, B_PACKET_OK_SUBTYPE_SHORTCUT);
b_conn_send_packet (node->conn, pkt);
return;
/* Send error */
send_error:
pkt = b_packet_new_error (node->conn, B_PACKET_ERROR_SUBTYPE_SHORTCUT);
b_conn_send_packet (node->conn, pkt);
}
static void
receive_ok_shortcut (BConn* conn, BPacket* packet, gpointer user_data)
{
BtpNode* node = (BtpNode*) user_data;
/* Ignore if not adding this shortcut */
if ( !node->shortcut_add_timeout )
return;
/* Cancel switch timeout */
rand_timer_cancel (&node->shortcut_add_timeout );
/* Ignore if node is now a neighbor (shouldn't happen) */
if ( btp_tree_is_parent(node) || btp_tree_is_child(node) )
return;
/* Add to shortcuts list (if not already in list) */
if ( btp_tree_is_shortcut(node) )
return;
/* Add to shortcuts list */
btp_tree_add_shortcut (node);
}
static void
receive_error_shortcut (BConn* conn, BPacket* packet, gpointer user_data)
{
BtpNode* node = (BtpNode*) user_data;
/* Ignore if not adding shortcut */
if ( !node->shortcut_add_timeout )
return;
/* Cancel switch timeout */
rand_timer_cancel (&node->shortcut_add_timeout);
}
static gboolean
shortcut_add_timeout_cb (gpointer data)
{
BtpNode* node = (BtpNode*) data;
BTPP (12, "SC: Shortcut add timeout to %s:%d\n", node->hostname, node->port);
node->shortcut_add_timeout = 0;
return FALSE;
}
/* ************************************************************ */
/* Node info */
/* Send node information. Call periodically or when a neighbors or
shortcuts change. */
static void
send_node_info (BtpTree* tree)
{
BtpNode* node = tree->me;
BPacket* pkt;
BTPP (1, "send_node_info\n");
BTPP (13, "NI: Send node info\n");
g_return_if_fail (tree);
/* Don't send node info if we aren't using shortcuts */
if (!tree->use_shortcuts)
return;
/* Forward info to all neighbors */
pkt = b_packet_new_info_reply_node (NULL, node);
pkt->seq = g_htons(tree->group.seq_num++);
pkt->source_id = g_htonl(tree->group.source_id);
btp_tree_forward_mcast (TREE, NULL, pkt);
b_packet_delete (pkt);
/* Reset timer */
if (tree->send_node_info_timeout)
{
rand_timer_cancel (&tree->send_node_info_timeout);
rand_timer_set (&tree->send_node_info_timeout,
SEND_NODE_INFO_TIME, SEND_NODE_INFO_RANGE,
send_node_info_cb, tree);
}
}
static void
schedule_send_node_info (BtpTree* tree)
{
g_return_if_fail (tree);
BTPP (1, "schedule_send_node_info (%d)\n", tree->use_shortcuts);
/* Don't bother if we aren't using shortcuts */
if (!tree->use_shortcuts)
return;
rand_timer_set (&tree->send_node_info_timeout,
SEND_NODE_INFO_TIME, SEND_NODE_INFO_RANGE,
send_node_info_cb, tree);
}
static gboolean
send_node_info_cb (gpointer data)
{
BtpTree* tree = (BtpTree*) data;
guint degree;
BTPP (1, "send_node_info_cb\n");
/* Send node info only if we have room for shortcuts */
degree = btp_tree_degree (tree);
if (degree < tree->max_degree)
send_node_info (tree);
return FALSE;
}
static void
receive_reply_node (BConn* conn, BPacket* packet, gpointer user_data)
{
BtpNode* node = (BtpNode*) user_data;
guint32 distance;
gchar* hostname;
guint port;
gboolean rv;
BtpNode* anode; /* Announcing node */
GSList* i;
BTPP (1, "receive_reply_node\n");
/* Check if duplicate */
if (seq_num_check(node, packet))
return;
/* Parse */
rv = b_packet_parse_info_reply_node (packet, &distance, &hostname, &port);
if (!rv)
{
g_warning ("Received malformed REPLY-NODE\n");
return;
}
BTPP (13, "NI: Receive %u %s:%d\n", distance, hostname, port);
/* Find announcing node and update the delay. Only do this if we
are using shortcuts. (We will include these messages anyway in
case someone is making measurements.) */
anode = btp_tree_find_node (TREE, hostname, port);
if (!anode)
anode = btp_node_new (TREE, hostname, port, NULL);
g_free (hostname);
/* Update distance */
if (conn->distance)
distance += conn->distance;
else
distance += 10; /* Assume 10 ms delay if we don't know delay */
/* Save the delay */
anode->overlay_distance = distance;
BTPP (13, "NI: Overlay distance for %s:%d is %d\n",
anode->hostname, anode->port, distance);
/* Forward the packet */
# define SEND_PKT(N) do{ \
if ((N) != node) { \
BPacket* pkt = b_packet_clone (packet); \
g_assert ((N)->conn); \
pkt->id = (N)->conn->out_conn_id; \
*(guint32*) pkt->data = g_htonl(distance); \
b_conn_send_packet ((N)->conn, pkt); } } while(0)
/* Send to parent */
if (TREE->parent)
SEND_PKT(TREE->parent);
/* Send to children */
for (i = TREE->children; i != NULL; i = i->next)
SEND_PKT ((BtpNode*) i->data);
/* Send to shortcuts */
for (i = TREE->shortcuts; i != NULL; i = i->next)
SEND_PKT ((BtpNode*) i->data);
# undef SEND_PACKET
}
static void
receive_shortcut_remove (BConn* conn, BPacket* packet, gpointer user_data)
{
BtpNode* node = (BtpNode*) user_data;
if ( btp_tree_is_shortcut(node) )
btp_tree_remove_shortcut (node);
}
syntax highlighted by Code2HTML, v. 0.9.1