The following commit has been merged in the master branch: commit 7493b6a9ece567be7b17adf4110e6a6aa45837cd Author: Marek Lindner lindner_marek@yahoo.de Date: Fri Mar 9 23:43:14 2007 +0100
batman.c code partly moved into orginator.c and schedule.c for better overview orginators are stored a hash instead of a list
diff --git a/Makefile b/Makefile index fa0a8e4..870c0a2 100644 --- a/Makefile +++ b/Makefile @@ -31,23 +31,23 @@ LDFLAGS = -lpthread UNAME=$(shell uname)
ifeq ($(UNAME),Linux) -OS_OBJ= posix-specific.o posix.o linux-specific.o linux.o allocate.o bitarray.o +OS_OBJ= orginator.o schedule.o posix-specific.o posix.o linux-specific.o linux.o allocate.o bitarray.o hash.o endif
ifeq ($(UNAME),Darwin) -OS_OBJ= posix-specific.o posix.o bsd.o allocate.o bitarray.o +OS_OBJ= orginator.o schedule.o posix-specific.o posix.o bsd.o allocate.o bitarray.o hash.o endif
ifeq ($(UNAME),FreeBSD) -OS_OBJ= posix-specific.o posix.o bsd.o allocate.o bitarray.o +OS_OBJ= orginator.o schedule.o posix-specific.o posix.o bsd.o allocate.o bitarray.o hash.o endif
ifeq ($(UNAME),OpenBSD) -OS_OBJ= posix-specific.o posix.o bsd.o allocate.o bitarray.o +OS_OBJ= orginator.o schedule.o posix-specific.o posix.o bsd.o allocate.o bitarray.o hash.o endif
-LINUX_SRC_C= batman.c posix-specific.c posix.c linux-specific.c linux.c allocate.c bitarray.c -LINUX_SRC_H= batman.h batman-specific.h list.h os.h allocate.h bitarray.h +LINUX_SRC_C= batman.c orginator.c schedule.c posix-specific.c posix.c linux-specific.c linux.c allocate.c bitarray.c hash.c +LINUX_SRC_H= batman.h orginator.h schedule.h batman-specific.h list.h os.h allocate.h bitarray.h hash.h
all: batmand
diff --git a/batman.c b/batman.c index a064718..9188dd9 100644 --- a/batman.c +++ b/batman.c @@ -27,7 +27,10 @@ #include "os.h" #include "list.h" #include "batman.h" -#include "allocate.h" +#include "orginator.h" +#include "schedule.h" + +
/* "-d" is the command line switch for the debug level, * specify it multiple times to increase verbosity @@ -99,10 +102,10 @@ uint8_t found_ifs = 0; int32_t receive_max_sock = 0; fd_set receive_wait_set;
+struct hashtable_t *orig_hash;
-static LIST_HEAD(orig_list); -static LIST_HEAD(forw_list); -static LIST_HEAD(gw_list); +LIST_HEAD(forw_list); +LIST_HEAD(gw_list); LIST_HEAD(if_list); LIST_HEAD(hna_list);
@@ -177,42 +180,6 @@ void verbose_usage( void ) {
-/* this function finds or creates an originator entry for the given address if it does not exits */ -struct orig_node *get_orig_node( uint32_t addr ) { - - struct list_head *pos; - struct orig_node *orig_node; - - list_for_each( pos, &orig_list ) { - - orig_node = list_entry( pos, struct orig_node, list ); - - if ( orig_node->orig == addr ) - return orig_node; - - } - - debug_output( 4, "Creating new originator\n" ); - - orig_node = debugMalloc( sizeof(struct orig_node), 101 ); - memset(orig_node, 0, sizeof(struct orig_node)); - INIT_LIST_HEAD(&orig_node->list); - INIT_LIST_HEAD(&orig_node->neigh_list); - - orig_node->orig = addr; - orig_node->router = NULL; - - orig_node->bidirect_link = debugMalloc( found_ifs * sizeof(uint32_t), 102 ); - memset( orig_node->bidirect_link, 0, found_ifs * sizeof(uint32_t) ); - - list_add_tail( &orig_node->list, &orig_list ); - - return orig_node; - -} - - - void add_del_hna( struct orig_node *orig_node, int8_t del ) {
uint16_t hna_buff_count = 0; @@ -242,7 +209,7 @@ void add_del_hna( struct orig_node *orig_node, int8_t del ) {
-static void choose_gw() { +void choose_gw() {
struct list_head *pos; struct gw_node *gw_node, *tmp_curr_gw = NULL; @@ -353,7 +320,7 @@ static void choose_gw() {
-static void update_routes( struct orig_node *orig_node, struct neigh_node *neigh_node, unsigned char *hna_recv_buff, int16_t hna_buff_len ) { +void update_routes( struct orig_node *orig_node, struct neigh_node *neigh_node, unsigned char *hna_recv_buff, int16_t hna_buff_len ) {
static char orig_str[ADDR_STR_LEN], next_str[ADDR_STR_LEN];
@@ -403,7 +370,7 @@ static void update_routes( struct orig_node *orig_node, struct neigh_node *neigh /* add new announced network(s) */ if ( hna_buff_len > 0 ) {
- orig_node->hna_buff = debugMalloc( hna_buff_len, 103 ); + orig_node->hna_buff = debugMalloc( hna_buff_len, 101 ); orig_node->hna_buff_len = hna_buff_len;
memmove( orig_node->hna_buff, hna_recv_buff, hna_buff_len ); @@ -426,7 +393,7 @@ static void update_routes( struct orig_node *orig_node, struct neigh_node *neigh
if ( hna_buff_len > 0 ) {
- orig_node->hna_buff = debugMalloc( hna_buff_len, 104 ); + orig_node->hna_buff = debugMalloc( hna_buff_len, 102 ); orig_node->hna_buff_len = hna_buff_len;
memcpy( orig_node->hna_buff, hna_recv_buff, hna_buff_len ); @@ -443,7 +410,7 @@ static void update_routes( struct orig_node *orig_node, struct neigh_node *neigh
-static void update_gw_list( struct orig_node *orig_node, uint8_t new_gwflags ) { +void update_gw_list( struct orig_node *orig_node, uint8_t new_gwflags ) {
struct list_head *gw_pos, *gw_pos_tmp; struct gw_node *gw_node; @@ -481,7 +448,7 @@ static void update_gw_list( struct orig_node *orig_node, uint8_t new_gwflags ) { addr_to_string( orig_node->orig, orig_str, ADDR_STR_LEN ); debug_output( 3, "Found new gateway %s -> class: %i - %s\n", orig_str, new_gwflags, gw2string[new_gwflags] );
- gw_node = debugMalloc( sizeof(struct gw_node), 105 ); + gw_node = debugMalloc( sizeof(struct gw_node), 103 ); memset( gw_node, 0, sizeof(struct gw_node) ); INIT_LIST_HEAD( &gw_node->list );
@@ -497,136 +464,17 @@ static void update_gw_list( struct orig_node *orig_node, uint8_t new_gwflags ) {
-void debug() { +int isDuplicate( struct orig_node *orig_node, uint16_t seqno ) {
- struct list_head *forw_pos, *orig_pos, *neigh_pos; - struct forw_node *forw_node; - struct orig_node *orig_node; - struct neigh_node *neigh_node; - struct gw_node *gw_node; - uint16_t batman_count = 0; - static char str[ADDR_STR_LEN], str2[ADDR_STR_LEN]; - - - if ( debug_clients.clients_num[1] > 0 ) { - - debug_output( 2, "BOD\n" ); - - if ( list_empty( &gw_list ) ) { - - debug_output( 2, "No gateways in range ...\n" ); - - } else { - - list_for_each( orig_pos, &gw_list ) { - - gw_node = list_entry( orig_pos, struct gw_node, list ); - - if ( gw_node->deleted ) - continue; - - addr_to_string( gw_node->orig_node->orig, str, sizeof (str) ); - addr_to_string( gw_node->orig_node->router->addr, str2, sizeof (str2) ); - - if ( curr_gateway == gw_node ) { - debug_output( 2, "=> %s via: %s(%i), gw_class %i - %s, reliability: %i\n", str, str2, gw_node->orig_node->router->packet_count, gw_node->orig_node->gwflags, gw2string[gw_node->orig_node->gwflags], gw_node->unavail_factor ); - } else { - debug_output( 2, "%s via: %s(%i), gw_class %i - %s, reliability: %i\n", str, str2, gw_node->orig_node->router->packet_count, gw_node->orig_node->gwflags, gw2string[gw_node->orig_node->gwflags], gw_node->unavail_factor ); - } - - } - - if ( batman_count == 0 ) - debug_output( 2, "No gateways in range ...\n" ); - - } - - } - - if ( ( debug_clients.clients_num[0] > 0 ) || ( debug_clients.clients_num[3] > 0 ) ) { - - debug_output( 1, "BOD\n" ); - - if ( debug_clients.clients_num[3] > 0 ) { - - debug_output( 4, "------------------ DEBUG ------------------\n" ); - debug_output( 4, "Forward list\n" ); - - list_for_each( forw_pos, &forw_list ) { - forw_node = list_entry( forw_pos, struct forw_node, list ); - addr_to_string( ((struct packet *)forw_node->pack_buff)->orig, str, sizeof (str) ); - debug_output( 4, " %s at %u\n", str, forw_node->send_time ); - } - - debug_output( 4, "Originator list\n" ); - - } - - list_for_each( orig_pos, &orig_list ) { - orig_node = list_entry( orig_pos, struct orig_node, list ); - - if ( orig_node->router == NULL ) - continue; - - batman_count++; - - addr_to_string( orig_node->orig, str, sizeof (str) ); - addr_to_string( orig_node->router->addr, str2, sizeof (str2) ); - - debug_output( 1, "%s, GW: %s(%i) via:", str, str2, orig_node->router->packet_count ); - debug_output( 4, "%s, GW: %s(%i), last_aware:%u via:\n", str, str2, orig_node->router->packet_count, orig_node->last_aware ); - - list_for_each( neigh_pos, &orig_node->neigh_list ) { - neigh_node = list_entry( neigh_pos, struct neigh_node, list ); - - addr_to_string( neigh_node->addr, str, sizeof (str) ); - - debug_output( 1, " %s(%i)", str, neigh_node->packet_count ); - debug_output( 4, "\t\t%s (%d)\n", str, neigh_node->packet_count ); - - } - - debug_output( 1, "\n" ); - - } - - if ( batman_count == 0 ) { - - debug_output( 1, "No batman nodes in range ...\n" ); - debug_output( 4, "No batman nodes in range ...\n" ); - - } - - debug_output( 4, "---------------------------------------------- END DEBUG\n" ); - - } - -} - - - -int isDuplicate( uint32_t orig, uint16_t seqno ) { - - struct list_head *orig_pos, *neigh_pos; - struct orig_node *orig_node; + struct list_head *neigh_pos; struct neigh_node *neigh_node;
- list_for_each( orig_pos, &orig_list ) { - orig_node = list_entry( orig_pos, struct orig_node, list ); - - if ( orig == orig_node->orig ) { - - list_for_each( neigh_pos, &orig_node->neigh_list ) { - neigh_node = list_entry( neigh_pos, struct neigh_node, list ); - - if ( get_bit_status( neigh_node->seq_bits, orig_node->last_seqno, seqno ) ) - return 1; - - } + list_for_each( neigh_pos, &orig_node->neigh_list ) {
- return 0; + neigh_node = list_entry( neigh_pos, struct neigh_node, list );
- } + if ( get_bit_status( neigh_node->seq_bits, orig_node->last_seqno, seqno ) ) + return 1;
}
@@ -647,434 +495,18 @@ int isBidirectionalNeigh( struct orig_node *orig_neigh_node, struct batman_if *i
-void update_originator( struct orig_node *orig_node, struct packet *in, uint32_t neigh, struct batman_if *if_incoming, unsigned char *hna_recv_buff, int16_t hna_buff_len ) { - - struct list_head *neigh_pos; - struct neigh_node *neigh_node = NULL, *tmp_neigh_node, *best_neigh_node; - uint8_t max_packet_count = 0, is_new_seqno = 0; - - - debug_output( 4, "update_originator(): Searching and updating originator entry of received packet, \n" ); - - - list_for_each( neigh_pos, &orig_node->neigh_list ) { - - tmp_neigh_node = list_entry( neigh_pos, struct neigh_node, list ); - - if ( ( tmp_neigh_node->addr == neigh ) && ( tmp_neigh_node->if_incoming == if_incoming ) ) { - - neigh_node = tmp_neigh_node; - - } else { - - bit_get_packet( tmp_neigh_node->seq_bits, in->seqno - orig_node->last_seqno, 0 ); - tmp_neigh_node->packet_count = bit_packet_count( tmp_neigh_node->seq_bits ); - - if ( tmp_neigh_node->packet_count > max_packet_count ) { - - max_packet_count = tmp_neigh_node->packet_count; - best_neigh_node = tmp_neigh_node; - - } - - } - - } - - if ( neigh_node == NULL ) { - - debug_output( 4, "Creating new last-hop neighbour of originator\n" ); - - neigh_node = debugMalloc( sizeof (struct neigh_node), 106 ); - memset( neigh_node, 0, sizeof(struct neigh_node) ); - INIT_LIST_HEAD( &neigh_node->list ); - - neigh_node->addr = neigh; - neigh_node->if_incoming = if_incoming; - - list_add_tail( &neigh_node->list, &orig_node->neigh_list ); - - } else { - - debug_output( 4, "Updating existing last-hop neighbour of originator\n" ); - - } - - - is_new_seqno = bit_get_packet( neigh_node->seq_bits, in->seqno - orig_node->last_seqno, 1 ); - neigh_node->packet_count = bit_packet_count( neigh_node->seq_bits ); - - if ( neigh_node->packet_count > max_packet_count ) { - - max_packet_count = neigh_node->packet_count; - best_neigh_node = neigh_node; - - } - - - neigh_node->last_aware = get_time(); - - if ( is_new_seqno ) { - - debug_output( 4, "updating last_seqno: old %d, new %d \n", orig_node->last_seqno, in->seqno ); - - orig_node->last_seqno = in->seqno; - neigh_node->last_ttl = in->ttl; - - } - - /* update routing table and check for changed hna announcements */ - update_routes( orig_node, best_neigh_node, hna_recv_buff, hna_buff_len ); - - if ( orig_node->gwflags != in->gwflags ) - update_gw_list( orig_node, in->gwflags ); - - orig_node->gwflags = in->gwflags; - -} - - - -void schedule_own_packet( struct batman_if *batman_if ) { - - struct forw_node *forw_node_new, *forw_packet_tmp = NULL; - struct list_head *list_pos; - - - forw_node_new = debugMalloc( sizeof(struct forw_node), 107 ); - - INIT_LIST_HEAD( &forw_node_new->list ); - - forw_node_new->send_time = get_time() + orginator_interval - JITTER + rand_num( 2 * JITTER ); - forw_node_new->if_outgoing = batman_if; - forw_node_new->own = 1; - - if ( num_hna > 0 ) { - - forw_node_new->pack_buff = debugMalloc( sizeof(struct packet) + num_hna * 5 * sizeof(unsigned char), 108 ); - memcpy( forw_node_new->pack_buff, (unsigned char *)&batman_if->out, sizeof(struct packet) ); - memcpy( forw_node_new->pack_buff + sizeof(struct packet), hna_buff, num_hna * 5 * sizeof(unsigned char) ); - forw_node_new->pack_buff_len = sizeof(struct packet) + num_hna * 5 * sizeof(unsigned char); - - } else { - - forw_node_new->pack_buff = debugMalloc( sizeof(struct packet), 109 ); - memcpy( forw_node_new->pack_buff, &batman_if->out, sizeof(struct packet) ); - forw_node_new->pack_buff_len = sizeof(struct packet); - - } - - list_for_each( list_pos, &forw_list ) { - - forw_packet_tmp = list_entry( list_pos, struct forw_node, list ); - - if ( forw_packet_tmp->send_time > forw_node_new->send_time ) { - - list_add_before( &forw_list, list_pos, &forw_node_new->list ); - break; - - } - - } - - if ( ( forw_packet_tmp == NULL ) || ( forw_packet_tmp->send_time <= forw_node_new->send_time ) ) - list_add_tail( &forw_node_new->list, &forw_list ); - - batman_if->out.seqno++; - -} - - - -void schedule_forward_packet( struct packet *in, uint8_t unidirectional, uint8_t directlink, unsigned char *hna_recv_buff, int16_t hna_buff_len, struct batman_if *if_outgoing ) { - - struct forw_node *forw_node_new; - - debug_output( 4, "schedule_forward_packet(): \n" ); - - if ( in->ttl <= 1 ) { - - debug_output( 4, "ttl exceeded \n" ); - - } else { - - forw_node_new = debugMalloc( sizeof(struct forw_node), 110 ); - - INIT_LIST_HEAD(&forw_node_new->list); - - if ( hna_buff_len > 0 ) { - - forw_node_new->pack_buff = debugMalloc( sizeof(struct packet) + hna_buff_len, 111 ); - memcpy( forw_node_new->pack_buff, in, sizeof(struct packet) ); - memcpy( forw_node_new->pack_buff + sizeof(struct packet), hna_recv_buff, hna_buff_len ); - forw_node_new->pack_buff_len = sizeof(struct packet) + hna_buff_len; - - } else { - - forw_node_new->pack_buff = debugMalloc( sizeof(struct packet), 112 ); - memcpy( forw_node_new->pack_buff, in, sizeof(struct packet) ); - forw_node_new->pack_buff_len = sizeof(struct packet); - - } - - - ((struct packet *)forw_node_new->pack_buff)->ttl--; - forw_node_new->send_time = get_time(); - forw_node_new->own = 0; - - forw_node_new->if_outgoing = if_outgoing; - - if ( unidirectional ) { - - ((struct packet *)forw_node_new->pack_buff)->flags = ( UNIDIRECTIONAL | DIRECTLINK ); - - } else if ( directlink ) { - - ((struct packet *)forw_node_new->pack_buff)->flags = DIRECTLINK; - - } else { - - ((struct packet *)forw_node_new->pack_buff)->flags = 0x00; - - } - - list_add( &forw_node_new->list, &forw_list ); - - } - -} - - - -void send_outstanding_packets() { - - struct forw_node *forw_node; - struct list_head *forw_pos, *if_pos, *temp; - struct batman_if *batman_if; - static char orig_str[ADDR_STR_LEN]; - uint8_t directlink; - uint32_t curr_time; - - - if ( list_empty( &forw_list ) ) - return; - - curr_time = get_time(); - - list_for_each_safe( forw_pos, temp, &forw_list ) { - forw_node = list_entry( forw_pos, struct forw_node, list ); - - if ( forw_node->send_time <= curr_time ) { - - addr_to_string( ((struct packet *)forw_node->pack_buff)->orig, orig_str, ADDR_STR_LEN ); - - directlink = ( ( ((struct packet *)forw_node->pack_buff)->flags & DIRECTLINK ) ? 1 : 0 ); - - ((struct packet *)forw_node->pack_buff)->seqno = htons( ((struct packet *)forw_node->pack_buff)->seqno ); /* change sequence number to network order */ - - - if ( ((struct packet *)forw_node->pack_buff)->flags & UNIDIRECTIONAL ) { - - if ( forw_node->if_outgoing != NULL ) { - - debug_output( 4, "Forwarding packet (originator %s, seqno %d, TTL %d) on interface %s\n", orig_str, ntohs( ((struct packet *)forw_node->pack_buff)->seqno ), ((struct packet *)forw_node->pack_buff)->ttl, forw_node->if_outgoing->dev ); - - if ( send_packet( forw_node->pack_buff, forw_node->pack_buff_len, &forw_node->if_outgoing->broad, forw_node->if_outgoing->udp_send_sock ) < 0 ) { - exit( -1 ); - } - - } else { - - debug_output( 0, "Error - can't forward packet with UDF: outgoing iface not specified \n" ); - - } - - /* multihomed peer assumed */ - } else if ( ( directlink ) && ( ((struct packet *)forw_node->pack_buff)->ttl == 1 ) ) { - - if ( ( forw_node->if_outgoing != NULL ) ) { - - if ( send_packet( forw_node->pack_buff, forw_node->pack_buff_len, &forw_node->if_outgoing->broad, forw_node->if_outgoing->udp_send_sock ) < 0 ) { - exit( -1 ); - } - - } else { - - debug_output( 0, "Error - can't forward packet with IDF: outgoing iface not specified (multihomed) \n" ); - - } - - } else { - - if ( ( directlink ) && ( forw_node->if_outgoing == NULL ) ) { - - debug_output( 0, "Error - can't forward packet with IDF: outgoing iface not specified \n" ); - - } else { - - list_for_each(if_pos, &if_list) { - - batman_if = list_entry(if_pos, struct batman_if, list); - - if ( ( directlink ) && ( forw_node->if_outgoing == batman_if ) ) { - ((struct packet *)forw_node->pack_buff)->flags = DIRECTLINK; - } else { - ((struct packet *)forw_node->pack_buff)->flags = 0x00; - } - - debug_output( 4, "Forwarding packet (originator %s, seqno %d, TTL %d) on interface %s\n", orig_str, ntohs( ((struct packet *)forw_node->pack_buff)->seqno ), ((struct packet *)forw_node->pack_buff)->ttl, batman_if->dev ); - - /* non-primary interfaces do not send hna information */ - if ( ( forw_node->own ) && ( ((struct packet *)forw_node->pack_buff)->orig != ((struct batman_if *)if_list.next)->addr.sin_addr.s_addr ) ) { - - if ( send_packet( forw_node->pack_buff, sizeof(struct packet), &batman_if->broad, batman_if->udp_send_sock ) < 0 ) { - exit( -1 ); - } - - } else { - - if ( send_packet( forw_node->pack_buff, forw_node->pack_buff_len, &batman_if->broad, batman_if->udp_send_sock ) < 0 ) { - exit( -1 ); - } - - } - - } +void send_vis_packet() {
- } - - } - - list_del( forw_pos ); - - if ( forw_node->own ) - schedule_own_packet( forw_node->if_outgoing ); - - debugFree( forw_node->pack_buff, 1102 ); - debugFree( forw_node, 1103 ); - - } else { - - break; - - } - - } - -} - - - -void purge( uint32_t curr_time ) { - - struct list_head *orig_pos, *neigh_pos, *orig_temp, *neigh_temp; - struct list_head *gw_pos, *gw_pos_tmp; - struct orig_node *orig_node; - struct neigh_node *neigh_node; - struct gw_node *gw_node; - uint8_t gw_purged = 0; - static char orig_str[ADDR_STR_LEN]; - - debug_output( 4, "purge() \n" ); - - /* for all origins... */ - list_for_each_safe( orig_pos, orig_temp, &orig_list ) { - - orig_node = list_entry( orig_pos, struct orig_node, list ); - - if ( (int)( ( orig_node->last_aware + ( 2 * TIMEOUT ) ) < curr_time ) ) { - - addr_to_string(orig_node->orig, orig_str, ADDR_STR_LEN); - debug_output( 4, "Orginator timeout: originator %s, last_aware %u)\n", orig_str, orig_node->last_aware ); - - /* for all neighbours towards this orginator ... */ - list_for_each_safe( neigh_pos, neigh_temp, &orig_node->neigh_list ) { - neigh_node = list_entry(neigh_pos, struct neigh_node, list); - - list_del( neigh_pos ); - debugFree( neigh_node, 1104 ); - - } - - list_for_each_safe( gw_pos, gw_pos_tmp, &gw_list ) { - - gw_node = list_entry( gw_pos, struct gw_node, list ); - - if ( gw_node->deleted ) - continue; - - if ( gw_node->orig_node == orig_node ) { - - addr_to_string( gw_node->orig_node->orig, orig_str, ADDR_STR_LEN ); - debug_output( 3, "Removing gateway %s from gateway list\n", orig_str ); - - gw_node->deleted = get_time(); - - gw_purged = 1; - - break; - - } - - } - - list_del( orig_pos ); - - update_routes( orig_node, NULL, NULL, 0 ); - - debugFree( orig_node->bidirect_link, 1105 ); - debugFree( orig_node, 1106 ); - - } else { - - /* for all neighbours towards this orginator ... */ - list_for_each_safe( neigh_pos, neigh_temp, &orig_node->neigh_list ) { - - neigh_node = list_entry( neigh_pos, struct neigh_node, list ); - - if ( (int)( ( neigh_node->last_aware + ( 2 * TIMEOUT ) ) < curr_time ) ) { - - list_del( neigh_pos ); - debugFree( neigh_node, 1107 ); - - } - - } - - } - - } - - list_for_each_safe(gw_pos, gw_pos_tmp, &gw_list) { - - gw_node = list_entry(gw_pos, struct gw_node, list); - - if ( ( gw_node->deleted ) && ( (int)((gw_node->deleted + 3 * TIMEOUT) < curr_time) ) ) { - - list_del( gw_pos ); - debugFree( gw_pos, 1108 ); - - } - - } - - if ( gw_purged ) - choose_gw(); - -} - - - -void send_vis_packet() -{ - struct list_head *pos; + struct hash_it_t *hashit = NULL; struct orig_node *orig_node; unsigned char *packet=NULL;
int step = 5, size=0,cnt=0;
- list_for_each(pos, &orig_list) { - orig_node = list_entry(pos, struct orig_node, list); + while ( NULL != ( hashit = hash_iterate( orig_hash, hashit ) ) ) { + + orig_node = hashit->bucket->data; + if ( ( orig_node->router != NULL ) && ( orig_node->orig == orig_node->router->addr ) ) { if(cnt >= size) @@ -1090,10 +522,12 @@ void send_vis_packet() if(packet != NULL) { send_packet(packet, size * sizeof(unsigned char), &vis_if.addr, vis_if.sock); - debugFree( packet, 1109 ); + debugFree( packet, 1102 ); } }
+ + int8_t batman() {
struct list_head *if_pos, *neigh_pos, *hna_pos, *hna_pos_tmp, *forw_pos, *forw_pos_tmp; @@ -1114,6 +548,9 @@ int8_t batman() { debug_timeout = get_time(); bidirectional_timeout = orginator_interval * 3;
+ if ( NULL == ( orig_hash = hash_new( 128, orig_comp, orig_choose ) ) ) + return(-1); + if ( !( list_empty( &hna_list ) ) ) {
list_for_each( hna_pos, &hna_list ) { @@ -1296,7 +733,7 @@ int8_t batman() {
orig_neigh_node = get_orig_node( neigh );
- is_duplicate = isDuplicate( ((struct packet *)&in)->orig, ((struct packet *)&in)->seqno ); + is_duplicate = isDuplicate( orig_node, ((struct packet *)&in)->seqno ); is_bidirectional = isBidirectionalNeigh( orig_neigh_node, if_incoming );
/* update ranking */ @@ -1385,13 +822,13 @@ int8_t batman() {
send_outstanding_packets();
- purge( get_time() ); + purge_orginator( get_time() );
if ( debug_timeout + 1000 < get_time() ) {
debug_timeout = get_time();
- debug(); + debug_orginator();
checkIntegrity();
@@ -1404,22 +841,25 @@ int8_t batman() {
}
+ if ( debug_level > 0 ) printf( "Deleting all BATMAN routes\n" );
- purge( get_time() + ( 5 * TIMEOUT ) + orginator_interval ); + purge_orginator( get_time() + ( 5 * TIMEOUT ) + orginator_interval ); + + hash_delete( orig_hash );
list_for_each_safe( hna_pos, hna_pos_tmp, &hna_list ) {
hna_node = list_entry(hna_pos, struct hna_node, list);
- debugFree( hna_node, 1110 ); + debugFree( hna_node, 1103 );
}
if ( hna_buff != NULL ) - debugFree( hna_buff, 1111 ); + debugFree( hna_buff, 1104 );
list_for_each_safe( forw_pos, forw_pos_tmp, &forw_list ) { @@ -1427,8 +867,8 @@ int8_t batman() {
list_del( forw_pos );
- debugFree( forw_node->pack_buff, 1112 ); - debugFree( forw_node, 1113 ); + debugFree( forw_node->pack_buff, 1105 ); + debugFree( forw_node, 1106 );
}
diff --git a/batman.h b/batman.h index 3801b74..134eb23 100644 --- a/batman.h +++ b/batman.h @@ -26,6 +26,9 @@ #include <stdint.h> #include "list.h" #include "bitarray.h" +#include "hash.h" +#include "allocate.h" +
#define SOURCE_VERSION "0.2 alpha" @@ -73,12 +76,18 @@ extern uint8_t found_ifs; extern int32_t receive_max_sock; extern fd_set receive_wait_set;
+extern struct hashtable_t *orig_hash; + extern struct list_head if_list; extern struct list_head hna_list; +extern struct list_head gw_list; +extern struct list_head forw_list; extern struct vis_if vis_if; extern struct unix_if unix_if; extern struct debug_clients debug_clients;
+extern char *gw2string[]; + struct packet { uint32_t orig; @@ -91,8 +100,8 @@ struct packet
struct orig_node /* structure for orig_list maintaining nodes of mesh */ { - struct list_head list; uint32_t orig; + struct list_head list; struct neigh_node *router; struct batman_if *batman_if; uint32_t *bidirect_link; /* if node is a bidrectional neighbour, when my originator packet was broadcasted (replied) by this node and received by me */ @@ -204,9 +213,17 @@ struct curr_gw_data {
int8_t batman( void ); -void usage( void ); -void verbose_usage( void ); -void del_default_route(); +void usage( void ); +void verbose_usage( void ); +void update_routes( struct orig_node *orig_node, struct neigh_node *neigh_node, unsigned char *hna_recv_buff, int16_t hna_buff_len ); +void update_gw_list( struct orig_node *orig_node, uint8_t new_gwflags ); +void choose_gw(); +void del_default_route(); int8_t add_default_route(); +void debug_output( int8_t debug_prio, char *format, ... ); +uint32_t get_time( void ); +void addr_to_string( uint32_t addr, char *str, int32_t len ); +int32_t rand_num( int32_t limit ); +int8_t send_packet( unsigned char *packet_buff, int32_t packet_buff_len, struct sockaddr_in *broad, int32_t send_sock );
#endif diff --git a/hash.c b/hash.c new file mode 100644 index 0000000..067fe39 --- /dev/null +++ b/hash.c @@ -0,0 +1,263 @@ +/* Copyright (C) 2006 B.A.T.M.A.N. contributors: + * Simon Wunderlich + * This program is free software; you can redistribute it and/or + * modify it under the terms of version 2 of the GNU General Public + * License as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301, USA + * + */ + + +#include <stdio.h> /* NULL */ +#include "batman.h" + +/* clears the hash */ +void hash_init(struct hashtable_t *hash) { + int i; + hash->elements=0; + for (i=0 ; i<hash->size ; i++) { + hash->table[i].data= NULL; + hash->table[i].next= NULL; + } +} + + +/* remove the hash structure. if hashdata_free_cb != NULL, + * this function will be called to remove the elements inside of the hash. + * if you don't remove the elements, memory might be leaked. */ +/*void hash_delete(struct hashtable_t *hash, hashdata_free_cb free_cb) { + struct element_t *bucket, *last_bucket; + int i; + + for (i=0; i<hash->size; i++) { + if (hash->table[i].data != NULL) { + if (free_cb!=NULL) free_cb( hash->table[i].data ); + + bucket= hash->table[i].next; + while (bucket != NULL) { + if (free_cb!=NULL) free_cb( hash->table[i].data ); + last_bucket= bucket; + bucket= bucket->next; + debugFree(last_bucket, 1301); + } + } + } +}*/ + + + +/* FYI: purge deletes all elements within that structure but we should free the hash itself !*/ +void hash_delete(struct hashtable_t *hash) { + + debugFree( hash->table, 1301 ); + debugFree( hash, 1302 ); + +} + + + + +/* iterate though the hash. first element is selected with iter_in NULL. + * use the returned iterator to access the elements until hash_it_t returns NULL. */ +struct hash_it_t *hash_iterate(struct hashtable_t *hash, struct hash_it_t *iter_in) { + struct hash_it_t *iter; + + if (iter_in == NULL) { + iter= debugMalloc(sizeof(struct hash_it_t), 301); + iter->index = -1; + iter->bucket = NULL; + } else + iter= iter_in; + if ( iter->bucket!=NULL ) { + iter->bucket = iter->bucket->next; /* choose next */ + if (iter->bucket !=NULL) /* if fine, return it */ + return(iter); + } + iter->index++; + while ( iter->index < hash->size ) { /* go through the entries of the hash table */ + if ((hash->table[ iter->index ].data) != NULL){ + iter->bucket = &(hash->table[ iter->index ]); + return(iter); /* if this table entry is not null, return it */ + } else + iter->index++; /* else, go to the next */ + } + /* nothing to iterate over anymore */ + debugFree(iter, 1303); + return(NULL); +} + + +/* allocates and clears the hash */ +struct hashtable_t *hash_new(int size, hashdata_compare_cb compare, hashdata_choose_cb choose) { + struct hashtable_t *hash; + + hash= debugMalloc( sizeof(struct hashtable_t) , 302); + if ( hash == NULL ) /* could not allocate the hash control structure */ + return (NULL); + + hash->size= size; + hash->table= debugMalloc( sizeof(struct element_t) * size, 303); + if ( hash->table == NULL ) { /* could not allocate the table */ + debugFree(hash, 1304); + return(NULL); + } + hash->compare= compare; + hash->choose= choose; + return(hash); +} + + +/* adds data to the hashtable. returns 0 on success, -1 on error */ +int hash_add(struct hashtable_t *hash, void *data) { + int index; + struct element_t *bucket, *new_bucket; + + index = hash->choose( data , hash->size ); + bucket = &(hash->table[index]); + + if ( bucket->data==NULL ) { /* bucket is empty, put it in */ + bucket->data=data; + hash->elements++; + return(0); + } else { + new_bucket= bucket; + do { + if (0 == hash->compare( new_bucket->data, data )) { /* already added, don't add again */ + return(-1); + } + bucket= new_bucket; + new_bucket= bucket->next; + } while ( new_bucket!=NULL); + + /* found the tail of the list, add new element */ + if (NULL == (new_bucket= debugMalloc(sizeof(struct element_t),304))) + return(-1); /* debugMalloc failed */ + + new_bucket->data= data; /* init the new bucket */ + new_bucket->next= NULL; + bucket->next= new_bucket; /* and link it */ + hash->elements++; + return(0); + + } +} +/* finds data, based on the key in keydata. returns the found data on success, or NULL on error */ +void *hash_find(struct hashtable_t *hash, void *keydata) { + int index; + struct element_t *bucket; + + index = hash->choose( keydata , hash->size ); + bucket = &(hash->table[index]); + + if ( bucket->data!=NULL ) { + do { + if (0 == hash->compare( bucket->data, keydata )) { + return( bucket->data ); + } + bucket= bucket->next; + } while ( bucket!=NULL ); + } + return(NULL); + +} + + +/* removes data from hash, if found. returns pointer do data on success, + * so you can remove the used structure yourself, or NULL on error . + * data could be the structure you use with just the key filled, + * we just need the key for comparing. */ +void *hash_remove(struct hashtable_t *hash, void *data) { + int index; + struct element_t *bucket, *last_bucket; + void *data_save; + + index = hash->choose( data , hash->size ); + bucket = &(hash->table[index]); + + if (bucket->data != NULL) { + last_bucket=NULL; + do { + if (0 == hash->compare( bucket->data, data )) { /* found entry, delete it. */ + data_save = bucket->data; /* save the pointer to the data */ + if ( last_bucket == NULL ) { /* we're on the first entry */ + if ( bucket->next == NULL ) { /* there is no next bucket, nothing to preserve. */ + bucket->data= NULL; + } else { /* else, move the second bucket onto the first one */ + bucket->data= bucket->next->data; + bucket->next= bucket->next->next; + } + } else { /* not the first entry */ + last_bucket->next= bucket->next; + debugFree(bucket, 1305); + } + + hash->elements--; + return( data_save ); + } + last_bucket= bucket; + bucket= bucket->next; + } while (bucket!=NULL); + } + + return(NULL); +} + + +/* resize the hash, returns the pointer to the new hash or NULL on error. removes the old hash on success. */ +struct hashtable_t *hash_resize(struct hashtable_t *hash, int size) { + struct hashtable_t *new_hash; + struct element_t *bucket; + int i; + + /* initialize a new hash with the new size */ + if (NULL == (new_hash= hash_new(size, hash->compare, hash->choose))) + return(NULL); + + /* copy the elements */ + for (i=0; i<hash->size; i++) { + if (hash->table[i].data != NULL) { + hash_add( new_hash, hash->table[i].data ); + bucket= hash->table[i].next; + while (bucket != NULL) { + hash_add( new_hash, bucket->data ); + bucket= bucket->next; + } + } + } + hash_delete(hash); + + return( new_hash); + +} + + +/* print the hash table for debugging */ +void hash_debug( struct hashtable_t *hash) { + int i; + struct element_t *bucket; + for (i=0; i<hash->size;i++) { + printf("[%d] ",i); + if (hash->table[i].data != NULL) { + printf("[%10p] ", hash->table[i].data); + + + bucket= hash->table[i].next; + while (bucket != NULL) { + printf("-> [%10p] ", bucket->data); + bucket= bucket->next; + } + } + printf("\n"); + + } +} + diff --git a/hash.h b/hash.h new file mode 100644 index 0000000..8a05514 --- /dev/null +++ b/hash.h @@ -0,0 +1,79 @@ +/* Copyright (C) 2006 B.A.T.M.A.N. contributors: + * Simon Wunderlich + * This program is free software; you can redistribute it and/or + * modify it under the terms of version 2 of the GNU General Public + * License as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301, USA + * + */ + + +typedef int (*hashdata_compare_cb)(void *, void *); +typedef int (*hashdata_choose_cb)(void *, int); +typedef void (*hashdata_free_cb)(void *); + +struct element_t { + void *data; /* pointer to the data */ + struct element_t *next; /* overflow bucket pointer */ +}; + +struct hash_it_t { + int index; + struct element_t *bucket; +}; + +struct hashtable_t { + struct element_t *table; /* the hashtable itself, with the buckets */ + int elements; /* number of elements registered */ + int size; /* size of hashtable */ + hashdata_compare_cb compare; /* callback to a compare function. + * should compare 2 element datas for their keys, + * return 0 if same and not 0 if not same */ + hashdata_choose_cb choose; /* the hashfunction, should return an index based + * on the key in the data of the first argument + * and the size the second */ +}; + +/* clears the hash */ +void hash_init(struct hashtable_t *hash); + +/* allocates and clears the hash */ +struct hashtable_t *hash_new(int size, hashdata_compare_cb compare, hashdata_choose_cb choose); + +/* remove the hash structure. if hashdata_free_cb != NULL, + * this function will be called to remove the elements inside of the hash. + * if you don't remove the elements, memory might be leaked. */ +void hash_delete(struct hashtable_t *hash); + + +/* adds data to the hashtable. returns 0 on success, -1 on error */ +int hash_add(struct hashtable_t *hash, void *data); + +/* removes data from hash, if found. returns pointer do data on success, + * so you can remove the used structure yourself, or NULL on error . + * data could be the structure you use with just the key filled, + * we just need the key for comparing. */ +void *hash_remove(struct hashtable_t *hash, void *data); + +/* adds data to the hashtable. returns 0 on success, -1 on error */ +void *hash_find(struct hashtable_t *hash, void *keydata); + +/* resize the hash, returns the pointer to the new hash or NULL on error. removes the old hash on success */ +struct hashtable_t *hash_resize(struct hashtable_t *hash, int size); + +/* print the hash table for debugging */ +void hash_debug( struct hashtable_t *hash); + +/* iterate though the hash. first element is selected with iter_in NULL. + * use the returned iterator to access the elements until hash_it_t returns NULL. */ +struct hash_it_t *hash_iterate(struct hashtable_t *hash, struct hash_it_t *iter_in); + diff --git a/orginator.c b/orginator.c new file mode 100644 index 0000000..f4d59ca --- /dev/null +++ b/orginator.c @@ -0,0 +1,401 @@ +/* Copyright (C) 2006 B.A.T.M.A.N. contributors: + * Simon Wunderlich, Marek Lindner + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of version 2 of the GNU General Public + * License as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301, USA + * + */ + + + +#include <string.h> +#include "batman.h" + + + +/* needed for hash, compares 2 struct orig_node, but only their ip-addresses. assumes that + * the ip address is the first field in the struct */ +int orig_comp(void *data1, void *data2) { + + return(memcmp(data1, data2, 4)); + +} + + + +/* hashfunction to choose an entry in a hash table of given size */ +/* hash algorithm from http://en.wikipedia.org/wiki/Hash_table */ +int orig_choose(void *data, int32_t size) { + + unsigned char *key= data; + uint32_t hash = 0; + size_t i; + + for (i = 0; i < 4; i++) { + hash += key[i]; + hash += (hash << 10); + hash ^= (hash >> 6); + } + + hash += (hash << 3); + hash ^= (hash >> 11); + hash += (hash << 15); + + return (hash%size); + +} + + + +/* this function finds or creates an originator entry for the given address if it does not exits */ +struct orig_node *get_orig_node( uint32_t addr ) { + + struct orig_node *orig_node; + + + orig_node = ((struct orig_node *)hash_find( orig_hash, &addr )); + + if ( orig_node != NULL ) + return orig_node; + + + debug_output( 4, "Creating new originator\n" ); + + orig_node = debugMalloc( sizeof(struct orig_node), 401 ); + memset(orig_node, 0, sizeof(struct orig_node)); + INIT_LIST_HEAD(&orig_node->list); + INIT_LIST_HEAD(&orig_node->neigh_list); + + orig_node->orig = addr; + orig_node->router = NULL; + orig_node->batman_if = NULL; + + orig_node->bidirect_link = debugMalloc( found_ifs * sizeof(uint32_t), 402 ); + memset( orig_node->bidirect_link, 0, found_ifs * sizeof(uint32_t) ); + + hash_add(orig_hash, orig_node); + if (orig_hash->elements * 4 > orig_hash->size) { + struct hashtable_t *swaphash; + swaphash = hash_resize(orig_hash, orig_hash->size*2); + if (swaphash == NULL) + debug_output( 0, "Couldn't resize hash table\n" ); + else + orig_hash = swaphash; + + } + + return orig_node; + +} + + + +void update_originator( struct orig_node *orig_node, struct packet *in, uint32_t neigh, struct batman_if *if_incoming, unsigned char *hna_recv_buff, int16_t hna_buff_len ) { + + struct list_head *neigh_pos; + struct neigh_node *neigh_node = NULL, *tmp_neigh_node, *best_neigh_node; + uint8_t max_packet_count = 0, is_new_seqno = 0; + + + debug_output( 4, "update_originator(): Searching and updating originator entry of received packet, \n" ); + + + list_for_each( neigh_pos, &orig_node->neigh_list ) { + + tmp_neigh_node = list_entry( neigh_pos, struct neigh_node, list ); + + if ( ( tmp_neigh_node->addr == neigh ) && ( tmp_neigh_node->if_incoming == if_incoming ) ) { + + neigh_node = tmp_neigh_node; + + } else { + + bit_get_packet( tmp_neigh_node->seq_bits, in->seqno - orig_node->last_seqno, 0 ); + tmp_neigh_node->packet_count = bit_packet_count( tmp_neigh_node->seq_bits ); + + if ( tmp_neigh_node->packet_count > max_packet_count ) { + + max_packet_count = tmp_neigh_node->packet_count; + best_neigh_node = tmp_neigh_node; + + } + + } + + } + + if ( neigh_node == NULL ) { + + debug_output( 4, "Creating new last-hop neighbour of originator\n" ); + + neigh_node = debugMalloc( sizeof (struct neigh_node), 403 ); + memset( neigh_node, 0, sizeof(struct neigh_node) ); + INIT_LIST_HEAD( &neigh_node->list ); + + neigh_node->addr = neigh; + neigh_node->if_incoming = if_incoming; + + list_add_tail( &neigh_node->list, &orig_node->neigh_list ); + + } else { + + debug_output( 4, "Updating existing last-hop neighbour of originator\n" ); + + } + + + is_new_seqno = bit_get_packet( neigh_node->seq_bits, in->seqno - orig_node->last_seqno, 1 ); + neigh_node->packet_count = bit_packet_count( neigh_node->seq_bits ); + + if ( neigh_node->packet_count > max_packet_count ) { + + max_packet_count = neigh_node->packet_count; + best_neigh_node = neigh_node; + + } + + + neigh_node->last_aware = get_time(); + + if ( is_new_seqno ) { + + debug_output( 4, "updating last_seqno: old %d, new %d \n", orig_node->last_seqno, in->seqno ); + + orig_node->last_seqno = in->seqno; + neigh_node->last_ttl = in->ttl; + + } + + /* update routing table and check for changed hna announcements */ + update_routes( orig_node, best_neigh_node, hna_recv_buff, hna_buff_len ); + + if ( orig_node->gwflags != in->gwflags ) + update_gw_list( orig_node, in->gwflags ); + + orig_node->gwflags = in->gwflags; + +} + + + +void purge_orginator( uint32_t curr_time ) { + + struct hash_it_t *hashit = NULL; + struct list_head *neigh_pos, *neigh_temp; + struct list_head *gw_pos, *gw_pos_tmp; + struct orig_node *orig_node; + struct neigh_node *neigh_node; + struct gw_node *gw_node; + uint8_t gw_purged = 0; + static char orig_str[ADDR_STR_LEN]; + + debug_output( 4, "purge() \n" ); + + /* for all origins... */ + while ( NULL != ( hashit = hash_iterate( orig_hash, hashit ) ) ) { + + orig_node = hashit->bucket->data; + + if ( (int)( ( orig_node->last_aware + ( 2 * TIMEOUT ) ) < curr_time ) ) { + + addr_to_string(orig_node->orig, orig_str, ADDR_STR_LEN); + debug_output( 4, "Orginator timeout: originator %s, last_aware %u)\n", orig_str, orig_node->last_aware ); + + hash_remove( orig_hash, orig_node ); + + /* for all neighbours towards this orginator ... */ + list_for_each_safe( neigh_pos, neigh_temp, &orig_node->neigh_list ) { + neigh_node = list_entry(neigh_pos, struct neigh_node, list); + + list_del( neigh_pos ); + debugFree( neigh_node, 1401 ); + + } + + list_for_each( gw_pos, &gw_list ) { + + gw_node = list_entry( gw_pos, struct gw_node, list ); + + if ( gw_node->deleted ) + continue; + + if ( gw_node->orig_node == orig_node ) { + + addr_to_string( gw_node->orig_node->orig, orig_str, ADDR_STR_LEN ); + debug_output( 3, "Removing gateway %s from gateway list\n", orig_str ); + + gw_node->deleted = get_time(); + + gw_purged = 1; + + break; + + } + + } + + update_routes( orig_node, NULL, NULL, 0 ); + + debugFree( orig_node->bidirect_link, 1402 ); + debugFree( orig_node, 1403 ); + + } else { + + /* for all neighbours towards this orginator ... */ + list_for_each_safe( neigh_pos, neigh_temp, &orig_node->neigh_list ) { + + neigh_node = list_entry( neigh_pos, struct neigh_node, list ); + + if ( (int)( ( neigh_node->last_aware + ( 2 * TIMEOUT ) ) < curr_time ) ) { + + list_del( neigh_pos ); + debugFree( neigh_node, 1404 ); + + } + + } + + } + + } + + list_for_each_safe(gw_pos, gw_pos_tmp, &gw_list) { + + gw_node = list_entry(gw_pos, struct gw_node, list); + + if ( ( gw_node->deleted ) && ( (int)((gw_node->deleted + 3 * TIMEOUT) < curr_time) ) ) { + + list_del( gw_pos ); + debugFree( gw_pos, 1405 ); + + } + + } + + if ( gw_purged ) + choose_gw(); + +} + + + +void debug_orginator() { + + struct hash_it_t *hashit = NULL; + struct list_head *forw_pos, *orig_pos, *neigh_pos; + struct forw_node *forw_node; + struct orig_node *orig_node; + struct neigh_node *neigh_node; + struct gw_node *gw_node; + uint16_t batman_count = 0; + static char str[ADDR_STR_LEN], str2[ADDR_STR_LEN]; + + + if ( debug_clients.clients_num[1] > 0 ) { + + debug_output( 2, "BOD\n" ); + + if ( list_empty( &gw_list ) ) { + + debug_output( 2, "No gateways in range ...\n" ); + + } else { + + list_for_each( orig_pos, &gw_list ) { + + gw_node = list_entry( orig_pos, struct gw_node, list ); + + if ( gw_node->deleted ) + continue; + + addr_to_string( gw_node->orig_node->orig, str, sizeof (str) ); + addr_to_string( gw_node->orig_node->router->addr, str2, sizeof (str2) ); + + if ( curr_gateway == gw_node ) { + debug_output( 2, "=> %s via: %s(%i), gw_class %i - %s, reliability: %i\n", str, str2, gw_node->orig_node->router->packet_count, gw_node->orig_node->gwflags, gw2string[gw_node->orig_node->gwflags], gw_node->unavail_factor ); + } else { + debug_output( 2, "%s via: %s(%i), gw_class %i - %s, reliability: %i\n", str, str2, gw_node->orig_node->router->packet_count, gw_node->orig_node->gwflags, gw2string[gw_node->orig_node->gwflags], gw_node->unavail_factor ); + } + + } + + if ( batman_count == 0 ) + debug_output( 2, "No gateways in range ...\n" ); + + } + + } + + if ( ( debug_clients.clients_num[0] > 0 ) || ( debug_clients.clients_num[3] > 0 ) ) { + + debug_output( 1, "BOD\n" ); + + if ( debug_clients.clients_num[3] > 0 ) { + + debug_output( 4, "------------------ DEBUG ------------------\n" ); + debug_output( 4, "Forward list\n" ); + + list_for_each( forw_pos, &forw_list ) { + forw_node = list_entry( forw_pos, struct forw_node, list ); + addr_to_string( ((struct packet *)forw_node->pack_buff)->orig, str, sizeof (str) ); + debug_output( 4, " %s at %u\n", str, forw_node->send_time ); + } + + debug_output( 4, "Originator list\n" ); + + } + + while ( NULL != ( hashit = hash_iterate( orig_hash, hashit ) ) ) { + + orig_node = hashit->bucket->data; + + if ( orig_node->router == NULL ) + continue; + + batman_count++; + + addr_to_string( orig_node->orig, str, sizeof (str) ); + addr_to_string( orig_node->router->addr, str2, sizeof (str2) ); + + debug_output( 1, "%s, GW: %s(%i) via:", str, str2, orig_node->router->packet_count ); + debug_output( 4, "%s, GW: %s(%i), last_aware:%u via:\n", str, str2, orig_node->router->packet_count, orig_node->last_aware ); + + list_for_each( neigh_pos, &orig_node->neigh_list ) { + neigh_node = list_entry( neigh_pos, struct neigh_node, list ); + + addr_to_string( neigh_node->addr, str, sizeof (str) ); + + debug_output( 1, " %s(%i)", str, neigh_node->packet_count ); + debug_output( 4, "\t\t%s (%d)\n", str, neigh_node->packet_count ); + + } + + debug_output( 1, "\n" ); + + } + + if ( batman_count == 0 ) { + + debug_output( 1, "No batman nodes in range ...\n" ); + debug_output( 4, "No batman nodes in range ...\n" ); + + } + + debug_output( 4, "---------------------------------------------- END DEBUG\n" ); + + } + +} + + diff --git a/allocate.h b/orginator.h similarity index 59% copy from allocate.h copy to orginator.h index 979e9b5..ece749b 100644 --- a/allocate.h +++ b/orginator.h @@ -1,6 +1,6 @@ -/* - * Copyright (C) 2006 B.A.T.M.A.N. contributors: - * Thomas Lopatic, Corinna 'Elektra' Aichele, Axel Neumann, Marek Lindner +/* Copyright (C) 2006 B.A.T.M.A.N. contributors: + * Simon Wunderlich, Marek Lindner + * * This program is free software; you can redistribute it and/or * modify it under the terms of version 2 of the GNU General Public * License as published by the Free Software Foundation. @@ -18,16 +18,11 @@ */
-#ifndef _ALLOCATE_H -#define _ALLOCATE_H 1 -#include <stdint.h> - -
-void checkIntegrity(void); -void checkLeak(void); -void *debugMalloc(uint32_t length, int32_t tag); -void *debugRealloc(void *memory, uint32_t length, int32_t tag); -void debugFree(void *memoryParameter, int32_t tag); +int orig_comp(void *data1, void *data2); +int orig_choose(void *data, int32_t size); +struct orig_node *get_orig_node( uint32_t addr ); +void update_originator( struct orig_node *orig_node, struct packet *in, uint32_t neigh, struct batman_if *if_incoming, unsigned char *hna_recv_buff, int16_t hna_buff_len ); +void purge_orginator( uint32_t curr_time ); +void debug_orginator();
-#endif diff --git a/schedule.c b/schedule.c new file mode 100644 index 0000000..2fdb92f --- /dev/null +++ b/schedule.c @@ -0,0 +1,256 @@ +/* Copyright (C) 2006 B.A.T.M.A.N. contributors: + * Simon Wunderlich, Marek Lindner + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of version 2 of the GNU General Public + * License as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301, USA + * + */ + + + +#include <string.h> +#include <stdlib.h> +#include "batman.h" + + + +void schedule_own_packet( struct batman_if *batman_if ) { + + struct forw_node *forw_node_new, *forw_packet_tmp = NULL; + struct list_head *list_pos; + + + forw_node_new = debugMalloc( sizeof(struct forw_node), 501 ); + + INIT_LIST_HEAD( &forw_node_new->list ); + + forw_node_new->send_time = get_time() + orginator_interval - JITTER + rand_num( 2 * JITTER ); + forw_node_new->if_outgoing = batman_if; + forw_node_new->own = 1; + + if ( num_hna > 0 ) { + + forw_node_new->pack_buff = debugMalloc( sizeof(struct packet) + num_hna * 5 * sizeof(unsigned char), 502 ); + memcpy( forw_node_new->pack_buff, (unsigned char *)&batman_if->out, sizeof(struct packet) ); + memcpy( forw_node_new->pack_buff + sizeof(struct packet), hna_buff, num_hna * 5 * sizeof(unsigned char) ); + forw_node_new->pack_buff_len = sizeof(struct packet) + num_hna * 5 * sizeof(unsigned char); + + } else { + + forw_node_new->pack_buff = debugMalloc( sizeof(struct packet), 503 ); + memcpy( forw_node_new->pack_buff, &batman_if->out, sizeof(struct packet) ); + forw_node_new->pack_buff_len = sizeof(struct packet); + + } + + list_for_each( list_pos, &forw_list ) { + + forw_packet_tmp = list_entry( list_pos, struct forw_node, list ); + + if ( forw_packet_tmp->send_time > forw_node_new->send_time ) { + + list_add_before( &forw_list, list_pos, &forw_node_new->list ); + break; + + } + + } + + if ( ( forw_packet_tmp == NULL ) || ( forw_packet_tmp->send_time <= forw_node_new->send_time ) ) + list_add_tail( &forw_node_new->list, &forw_list ); + + batman_if->out.seqno++; + +} + + + +void schedule_forward_packet( struct packet *in, uint8_t unidirectional, uint8_t directlink, unsigned char *hna_recv_buff, int16_t hna_buff_len, struct batman_if *if_outgoing ) { + + struct forw_node *forw_node_new; + + debug_output( 4, "schedule_forward_packet(): \n" ); + + if ( in->ttl <= 1 ) { + + debug_output( 4, "ttl exceeded \n" ); + + } else { + + forw_node_new = debugMalloc( sizeof(struct forw_node), 504 ); + + INIT_LIST_HEAD(&forw_node_new->list); + + if ( hna_buff_len > 0 ) { + + forw_node_new->pack_buff = debugMalloc( sizeof(struct packet) + hna_buff_len, 505 ); + memcpy( forw_node_new->pack_buff, in, sizeof(struct packet) ); + memcpy( forw_node_new->pack_buff + sizeof(struct packet), hna_recv_buff, hna_buff_len ); + forw_node_new->pack_buff_len = sizeof(struct packet) + hna_buff_len; + + } else { + + forw_node_new->pack_buff = debugMalloc( sizeof(struct packet), 506 ); + memcpy( forw_node_new->pack_buff, in, sizeof(struct packet) ); + forw_node_new->pack_buff_len = sizeof(struct packet); + + } + + + ((struct packet *)forw_node_new->pack_buff)->ttl--; + forw_node_new->send_time = get_time(); + forw_node_new->own = 0; + + forw_node_new->if_outgoing = if_outgoing; + + if ( unidirectional ) { + + ((struct packet *)forw_node_new->pack_buff)->flags = ( UNIDIRECTIONAL | DIRECTLINK ); + + } else if ( directlink ) { + + ((struct packet *)forw_node_new->pack_buff)->flags = DIRECTLINK; + + } else { + + ((struct packet *)forw_node_new->pack_buff)->flags = 0x00; + + } + + list_add( &forw_node_new->list, &forw_list ); + + } + +} + + + +void send_outstanding_packets() { + + struct forw_node *forw_node; + struct list_head *forw_pos, *if_pos, *temp; + struct batman_if *batman_if; + static char orig_str[ADDR_STR_LEN]; + uint8_t directlink; + uint32_t curr_time; + + + if ( list_empty( &forw_list ) ) + return; + + curr_time = get_time(); + + list_for_each_safe( forw_pos, temp, &forw_list ) { + forw_node = list_entry( forw_pos, struct forw_node, list ); + + if ( forw_node->send_time <= curr_time ) { + + addr_to_string( ((struct packet *)forw_node->pack_buff)->orig, orig_str, ADDR_STR_LEN ); + + directlink = ( ( ((struct packet *)forw_node->pack_buff)->flags & DIRECTLINK ) ? 1 : 0 ); + + ((struct packet *)forw_node->pack_buff)->seqno = htons( ((struct packet *)forw_node->pack_buff)->seqno ); /* change sequence number to network order */ + + + if ( ((struct packet *)forw_node->pack_buff)->flags & UNIDIRECTIONAL ) { + + if ( forw_node->if_outgoing != NULL ) { + + debug_output( 4, "Forwarding packet (originator %s, seqno %d, TTL %d) on interface %s\n", orig_str, ntohs( ((struct packet *)forw_node->pack_buff)->seqno ), ((struct packet *)forw_node->pack_buff)->ttl, forw_node->if_outgoing->dev ); + + if ( send_packet( forw_node->pack_buff, forw_node->pack_buff_len, &forw_node->if_outgoing->broad, forw_node->if_outgoing->udp_send_sock ) < 0 ) { + exit(EXIT_FAILURE); + } + + } else { + + debug_output( 0, "Error - can't forward packet with UDF: outgoing iface not specified \n" ); + + } + + /* multihomed peer assumed */ + } else if ( ( directlink ) && ( ((struct packet *)forw_node->pack_buff)->ttl == 1 ) ) { + + if ( ( forw_node->if_outgoing != NULL ) ) { + + if ( send_packet( forw_node->pack_buff, forw_node->pack_buff_len, &forw_node->if_outgoing->broad, forw_node->if_outgoing->udp_send_sock ) < 0 ) { + exit(EXIT_FAILURE); + } + + } else { + + debug_output( 0, "Error - can't forward packet with IDF: outgoing iface not specified (multihomed) \n" ); + + } + + } else { + + if ( ( directlink ) && ( forw_node->if_outgoing == NULL ) ) { + + debug_output( 0, "Error - can't forward packet with IDF: outgoing iface not specified \n" ); + + } else { + + list_for_each(if_pos, &if_list) { + + batman_if = list_entry(if_pos, struct batman_if, list); + + if ( ( directlink ) && ( forw_node->if_outgoing == batman_if ) ) { + ((struct packet *)forw_node->pack_buff)->flags = DIRECTLINK; + } else { + ((struct packet *)forw_node->pack_buff)->flags = 0x00; + } + + debug_output( 4, "Forwarding packet (originator %s, seqno %d, TTL %d) on interface %s\n", orig_str, ntohs( ((struct packet *)forw_node->pack_buff)->seqno ), ((struct packet *)forw_node->pack_buff)->ttl, batman_if->dev ); + + /* non-primary interfaces do not send hna information */ + if ( ( forw_node->own ) && ( ((struct packet *)forw_node->pack_buff)->orig != ((struct batman_if *)if_list.next)->addr.sin_addr.s_addr ) ) { + + if ( send_packet( forw_node->pack_buff, sizeof(struct packet), &batman_if->broad, batman_if->udp_send_sock ) < 0 ) { + exit(EXIT_FAILURE); + } + + } else { + + if ( send_packet( forw_node->pack_buff, forw_node->pack_buff_len, &batman_if->broad, batman_if->udp_send_sock ) < 0 ) { + exit(EXIT_FAILURE); + } + + } + + } + + } + + } + + list_del( forw_pos ); + + if ( forw_node->own ) + schedule_own_packet( forw_node->if_outgoing ); + + debugFree( forw_node->pack_buff, 1501 ); + debugFree( forw_node, 1502 ); + + } else { + + break; + + } + + } + +} + + diff --git a/batman-specific.h b/schedule.h similarity index 65% copy from batman-specific.h copy to schedule.h index 47ebb22..4e11961 100644 --- a/batman-specific.h +++ b/schedule.h @@ -1,6 +1,6 @@ -/* - * Copyright (C) 2006 B.A.T.M.A.N. contributors: - * Thomas Lopatic, Corinna 'Elektra' Aichele, Axel Neumann, Marek Lindner +/* Copyright (C) 2006 B.A.T.M.A.N. contributors: + * Simon Wunderlich, Marek Lindner + * * This program is free software; you can redistribute it and/or * modify it under the terms of version 2 of the GNU General Public * License as published by the Free Software Foundation. @@ -18,4 +18,6 @@ */
-#include "batman.h" +void schedule_own_packet( struct batman_if *batman_if ); +void schedule_forward_packet( struct packet *in, uint8_t unidirectional, uint8_t directlink, unsigned char *hna_recv_buff, int16_t hna_buff_len, struct batman_if *if_outgoing ); +void send_outstanding_packets();