/* 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 #include #include #include #include #include #include #include #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):("")) 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 \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); }