home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
ftp.ee.lbl.gov
/
2014.05.ftp.ee.lbl.gov.tar
/
ftp.ee.lbl.gov
/
mrdebug.tar.Z
/
mrdebug.tar
/
build_adj.c
< prev
next >
Wrap
C/C++ Source or Header
|
1993-10-25
|
24KB
|
758 lines
/************************************************************************
PURPOSE: Graph Parser, build adjacency list.
DESCRIPTION:
This program reads in a file containing a description of
the network and another file containing a list of the
subnets. The name of the file to read is supplied as an
argument when the program is called. In the file,
the represention is:
Equivalent Nodes
= node1 node2 (these interfaces are at the same physical
site. Each line is assumed to only
contain 2 node names)
Non-responding Node
? node (this node did not respond to the mapper
query)
Edge of the Network
> node1 node2 info (the edge is from node1 to node2 the
info is [metric/threshold/type] where
type is one or more of down, disabled,
tunnel, querier, and srcrt)
METHODOLOGY:
The program first reads in the subnets. Then
the network description file is read through once to
determine the size of the adjacency list (number of
sites). The adjacency list is then allocated and the
interfaces are added to each node of the adjacency list.
Subnets for these interfaces and a hash table for
conversion from interface names to adjacency list nodes
are also built at this time.
The network description file is now reread to build the
network. Each edge is added to the adjacency list as
it is read in. If the destination node of the edge is
a node that did not respond to the mapper, add a backwards
edge also but mark it as questionable.
PROGRAMMER: Deb Agarwal 6/1993
***********************************************************************/
#include <stdio.h>
#include <string.h>
#include "types.h"
#include "mrhash.h"
#include "data_struct_proto.h"
#include "build_adj_proto.h"
/******* GLOBAL VARIABLES *********/
Ifc_list invisib_ifcs;
/********* EXTERNAL REFERENCES ***********/
extern int verbose;
/*******************************************************************
PROCEDURE: read_subnets( subnet_fl, subnets )
DESCRIPTION:
This program reads in the network subnets from a file.
The subnets as they are read in will be stored in a
linked list for future use. The subnet file is assumed
to be arranged by increasing mask size.
********************************************************************/
void read_subnets( char *subnet_fl, Ifc_list *subnets )
{
int args;
FILE *subnet_list;
char cur_line[MAXLINE];
Interface *cur_ifc;
NAME full_name;
/*
** open the subnet file
*/
if( !(subnet_list = fopen( subnet_fl, "r" )))
{
printf( "ERROR: Unable to open input file named %s\n", subnet_fl);
exit(-1);
}
subnets->number = 0;
subnets->first = NULL;
/*
** Read the file all the way through and get
** all the subnet names and determine their masks.
** They are sorted in decreasing mask order.
*/
while( fgets( cur_line, MAXLINE, subnet_list ) != NULL )
{
args = sscanf( cur_line, "%s", &full_name );
if( args < 1 )
continue;
cur_ifc = (Interface *)calloc( 1, sizeof( Interface ));
strcpy( cur_ifc->name, full_name );
inet_parse(full_name, &cur_ifc->address, &cur_ifc->mask);
if( cur_ifc->mask != 0xffffffff )
{
cur_ifc->next = subnets->first;
subnets->first = cur_ifc;
subnets->number++;
}
else
free( cur_ifc );
}
}
/*******************************************************************
PROCEDURE: read_file( edge_fl, net, subnets )
DESCRIPTION:
This program opens the file containing the network's
edge list and reads it in. It then allocates the
adjacency list and maps the ip
names to an internal representation and builds
mapping functions for going either direction.
*********************************************************************/
void read_file( char *edge_fl, Network *net, Ifc_list *subnets, long extra_nodes )
{
FILE *edge_list;
Ifc_list names;
char cur_line[MAXLINE];
char *line_type;
char *ip_name = 0, *ip_name2 = 0;
int i;
Interface *cur_ifc, *back_ifc, *temp_ifc;
Equivalence *first_equiv, *cur_equiv, *next_equiv;
HENTRY_t *ht_entry_p;
/*
** open the edge file
*/
if( !(edge_list = fopen( edge_fl, "r" )))
{
printf( "ERROR: Unable to open input file named %s\n", edge_fl);
exit(-1);
}
/*
** Initialize network structures that need to be initialized
*/
net->changes.number = 0;
net->changes.last = NULL;
names.number = 0;
names.first = NULL;
first_equiv = NULL;
/*
** First read the file all the way through and get
** all the ip names in a sorted linked list.
** They are sorted in reverse order and duplicates
** have been discarded. The list is stored in
** nodes.
*/
while( fgets( cur_line, MAXLINE, edge_list ) != NULL )
{
line_type = strtok( cur_line, " \t\n");
ip_name = strtok( NULL, " \t\n" );
if( line_type == NULL || ip_name == NULL )
continue;
insert_name( &names, ip_name );
switch( line_type[0] )
{
case '>':
/* Register both ends of the network connection */
ip_name = strtok( NULL, " \t\n" );
insert_name( &names, ip_name );
break;
case '=':
/* remember the nodes with multiple interfaces */
ip_name2 = strtok( NULL, " \t\n" );
insert_name( &names, ip_name2 );
add_equivalence( &first_equiv, ip_name, ip_name2 );
break;
case '?':
/* This node did not respond to the mapper query */
insert_name( &invisib_ifcs, ip_name );
break;
}
}
fclose( edge_list );
net->no_interfaces = names.number;
/*
** Now to delete the additional interfaces for each node
** that had an equivalence specified.
*/
for( cur_equiv = first_equiv; cur_equiv != NULL;
cur_equiv = cur_equiv->next )
if( cur_equiv->ifcs.first != NULL )
for( cur_ifc = cur_equiv->ifcs.first->next; cur_ifc != NULL;
cur_ifc = cur_ifc->next )
delete_name( &names, cur_ifc->name );
delete_name( &names, "0.0.0.0" );
net->no_nodes = names.number + subnets->number;
net->no_alloc = net->no_nodes + extra_nodes;
/*
** Allocate the adjacency list for the network
*/
net->adj_list = (Node *)calloc( net->no_alloc, sizeof(Node));
create_htable( &net->name_map, NAMEMAP_HTABLE_SIZE );
create_htable( &net->ip_map, NAMEMAP_HTABLE_SIZE );
/*
** Now to create nodes for each of the subnets and enter
** them in the map from internal node representations.
*/
cur_ifc = subnets->first;
for( i = 0; i < subnets->number; i++, cur_ifc = cur_ifc->next )
{
insert_htable( &net->name_map, cur_ifc->name, i, (long *)cur_ifc, NULL );
if( find_ip_name( cur_ifc->name, ip_name ))
insert_htable( &net->ip_map, ip_name, i, (long *)cur_ifc, cur_ifc->name );
net->adj_list[i].type = SUBNET;
}
/*
** Now to create the mapping from IP names to my
** own internal node representations. Since the IP
** names are not consecutive, they are stored in a
** hash table. Also create edges to the subnets for
** each of the interfaces that have a subnet. Assume
** for now these edges have metric = 1 and threshold = 1.
*/
cur_ifc = names.first;
for( i = subnets->number; i < (names.number+subnets->number); i++ )
{
temp_ifc = find_subnet( cur_ifc->name, subnets );
insert_htable( &net->name_map, cur_ifc->name, i, (long *)temp_ifc, NULL );
if( find_ip_name( cur_ifc->name, ip_name ))
insert_htable( &net->ip_map, ip_name, i, (long *)temp_ifc, cur_ifc->name );
net->adj_list[i].type = ROUTER;
if( temp_ifc != NULL )
{
/* Add the edge to the subnet node */
add_ifc( net, cur_ifc->name, temp_ifc->name, "[1/1/suspect]", TRUE );
add_ifc( net, temp_ifc->name, cur_ifc->name, "[0/0]", FALSE);
}
/*
** start with the assumption that subnet interfaces are suspect
** until find an input line indicating otherwise
*/
temp_ifc = cur_ifc;
cur_ifc = cur_ifc->next;
free( temp_ifc );
}
names.first = NULL;
/*
** Now to add the mapping entries for the equivalent IP names
*/
for( cur_equiv = first_equiv; cur_equiv != NULL; cur_equiv = next_equiv)
{
if( cur_equiv->ifcs.first != NULL )
{
ht_entry_p = lookup_htable( &net->name_map, cur_equiv->ifcs.first->name );
for( cur_ifc = cur_equiv->ifcs.first->next; cur_ifc != NULL;
cur_ifc = temp_ifc )
{
if( lookup_htable( &net->name_map, cur_ifc->name ) != NULL )
printf( "This entry already exists?\n");
back_ifc = find_subnet( cur_ifc->name, subnets );
insert_htable( &net->name_map, cur_ifc->name, ht_entry_p->index,
(long *)back_ifc, NULL );
if( find_ip_name( cur_ifc->name, ip_name ))
insert_htable( &net->ip_map, ip_name, ht_entry_p->index,
(long *)back_ifc, cur_ifc->name );
temp_ifc = cur_ifc->next;
if( back_ifc != NULL )
{
/* Add the edge to the subnet node */
add_ifc( net, cur_ifc->name, back_ifc->name, "[1/1/suspect]", TRUE );
add_ifc( net, back_ifc->name, cur_ifc->name, "[0/0]", FALSE);
}
free( cur_ifc );
}
free( cur_equiv->ifcs.first );
}
next_equiv = cur_equiv->next;
free( cur_equiv );
}
/*print_htable( &net->name_map );*/
}
/*****************************************************************************
**
PROGRAM: build_adj( file, network )
DESCRIPTION:
This program rereads the network description and
builds the adjacency list. Interfaces specified as 0.0.0.0
are assumed not to exist. Each tunnel is treated
as a separate interface for symmetry in using the
adjacency list later. The program assumes that neighbors
on each subnet are enumerated in the edge descriptions.
*******************************************************************************/
void build_adj( char *edge_fl, Network *net, FILE *out )
{
int args;
FILE *edge_list;
char cur_line[MAXLINE];
char line_type, other[MAXLINE];
NAME frm_ip_name, ip_name, temp_name;
HENTRY_t *ht_entry_p;
Interface *frm_ifc, *to_ifc;
/****** reopen the edge file *****/
if( !(edge_list = fopen( edge_fl, "r" )))
{
printf( "ERROR: Unable to open input file named %s\n", edge_fl);
exit(-1);
}
while( fgets( cur_line, MAXLINE, edge_list ) != NULL )
{
args = sscanf( cur_line, "%c", &line_type );
if( args < 1 )
continue;
if( line_type == '>' )
{/*
** Find the interface associated with the from address
*/
sscanf( cur_line, "%c%s%s%s", &line_type, frm_ip_name, ip_name, other );
/*
** If this edge has a 0.0.0.0 address as its to end,
** then do not add it to the graph. It was simply used
** to register the fact that this interface is a querier
** for the subnet.
*/
if( !find_ip_name( ip_name, temp_name ))
strcpy( temp_name, ip_name );
if( !strcmp( temp_name, "0.0.0.0" ))
{
ht_entry_p = lookup_htable( &net->name_map, frm_ip_name );
to_ifc = (Interface *)ht_entry_p->subnet;
if( to_ifc == NULL )
{
if( verbose )
printf( "subnet for %s unknown\n", frm_ip_name );
continue;
}
frm_ifc = find_ifc( net, NULL, frm_ip_name, to_ifc->name );
frm_ifc->type &= ~SUSPECT;
sscanf( other, "[%ld/%ld", &frm_ifc->metric, &frm_ifc->threshold );
/*printf( "other = %s\n", other );*/
if( strstr( other, "querier" ) != NULL )
frm_ifc->type |= QUERIER;
if( strstr( other, "down" ) != NULL )
frm_ifc->type |= DOWN;
if( strstr( other, "disabled" ) != NULL )
frm_ifc->type |= DISABLED;
continue;
}
/*
** Try to add this edge to the network as not suspect
** if a NULL is returned, the edge is already in the
** network.
*/
frm_ifc = add_ifc( net, frm_ip_name, ip_name, other, FALSE );
if( frm_ifc == NULL )
continue;
if( find_name( &invisib_ifcs, frm_ifc->to_name ) &&
(frm_ifc->type & TUNNEL))
{/*
** This interface did not respond to the mapper
** query so add the edge the other direction with
** unknown metric and threshold.
*/
to_ifc = add_ifc( net, ip_name, frm_ip_name, other, TRUE );
}
}
}
fclose( edge_list );
fflush( stdout );
}
/******************************************************************************
PROCEDURE: Print_adj( net, out )
DESCRIPTION:
This routine prints out the adjacency list of the given graph.
The form it uses is node -> node, node, node, . . .
It will print it using the original node numbers provided with
the graph. It will break long lines at 10 nodes.
*******************************************************************************/
void Print_adj( Network *net_p, FILE *out )
{
int i;
for( i=0; i< net_p->no_nodes;i++)
print_node( net_p, i, out );
}
/*******************************************************************************
FUNCTION: print_node( net, node, out )
DESCRIPTION:
This function prints out the adjacency list for the specified node.
*********************************************************************************/
void print_node( Network *net_p, int i, FILE *out )
{
Interface *curifc_p;
fprintf(out, "\nNODE %d: distance = %ld", i, net_p->adj_list[i].dist_vects.distance );
for( curifc_p = net_p->adj_list[i].interfaces.first; curifc_p != NULL;
curifc_p = curifc_p->next )
{
fprintf( out, "\nname=%s mask=%x type=%x m/t=%ld/%ld, ",
curifc_p->name, curifc_p->mask,
curifc_p->type, curifc_p->metric, curifc_p->threshold );
fprintf( out, "->");
fprintf( out, ", %s", curifc_p->to_name);
}
fprintf( out, "\n");
return;
}
/****************************************************************
This procedure finds the appropriate subnet associated with the
address passed in and returns a pointer to the subnet interface. If
multiple subnets match this address, the longest fit will be returned.
A value of NULL is returned if no match is found.
*****************************************************************/
Interface *find_subnet( NAME name, Ifc_list *subnets )
{
Interface *cur_ifc;
ADDRESS address, mask;
inet_parse( name, &address, &mask );
for( cur_ifc = subnets->first; cur_ifc != NULL; cur_ifc = cur_ifc->next)
{
if( (cur_ifc->mask & address) == cur_ifc->address )
return cur_ifc;
}
return NULL;
}
/**************************************************************************
FUNCTION: add_equivalence( Equivalence *equivs, NAME name1, NAME name2 )
DESCRIPTION:
This function adds an equivalence relation to the list of equivalent
interfaces. Each node has an equivalence structure that contains
a lisked list of interfaces that are equivalent. When a new equivalence
is to be added, the lists are first searched to determine if this is
a redundant entry.
****************************************************************************/
void add_equivalence( Equivalence **equivs, NAME name1, NAME name2 )
{
Equivalence *equiv1, *equiv2;
Interface *cur_ifc, *nxt_ifc;
equiv1 = NULL;
equiv2 = NULL;
/*
** Determine if either name1 or name2 are already listed in
** one of the equivalence structures.
*/
for( equiv1 = *equivs; equiv1 != NULL; equiv1 = equiv1->next )
if( find_name( &equiv1->ifcs, name1 ))
break;
for( equiv2 = *equivs; equiv2 != NULL; equiv2 = equiv2->next )
if( find_name( &equiv2->ifcs, name2 ))
break;
if( equiv1 != NULL )
{/*
** Name 1 is already listed as having at least one equivalent interface
*/
if( equiv1 == equiv2 )
/*
** This equivalence information is redundant
*/
return;
if( equiv2 != NULL )
{/*
** The two equivalence lists need to be combined.
*/
for( cur_ifc = equiv2->ifcs.first; cur_ifc != NULL; )
{
nxt_ifc = cur_ifc->next;
insert_ifc( &equiv1->ifcs, cur_ifc );
cur_ifc = nxt_ifc;
}
equiv2->ifcs.first = NULL;
equiv2->ifcs.number = 0;
}
else
/*
** name 2 is not in any equivalence lists so add it to
** node 1's list.
*/
insert_name( &equiv1->ifcs, name2 );
}
else if( equiv2 != NULL )
/*
** name 2 has at least one equiv. interface but name 1 had none
** so add name 1 to the list containing name 2.
*/
insert_name( &equiv2->ifcs, name1 );
else
{/*
** This equivalence represents a new node so either
** find an empty equivalence structure in the linked
** list or allocate a new equivalence structure
** and put the two names in its list.
*/
for( equiv1 = *equivs; equiv1 != NULL; equiv1 = equiv1->next )
if( equiv1->ifcs.number == 0 )
break;
if( equiv1 == NULL )
{
equiv1 = (Equivalence *)calloc( 1, sizeof( Equivalence ));
equiv1->next = *equivs;
*equivs = equiv1;
}
insert_name( &equiv1->ifcs, name1 );
insert_name( &equiv1->ifcs, name2 );
}
return;
}
/*************************************************************************
FUNCTION: add_ifc( net, frm_ifc, node1, ip_name, type )
DESCRIPTION:
This function adds an interface to the network if it did not already
exist.
**************************************************************************/
Interface *add_ifc( Network *net, NAME frm_name, NAME to_name, char *type, int suspect )
{
long ifc_type, ifc_metric, ifc_thresh;
ADDRESS to_addr, frm_addr, mask;
HENTRY_t *ht_entry_p;
Interface *new_ifc, *to_sub, *temp_ifc;
Node *node1;
/*
** Create a new edge and copy the information to it
*/
sscanf( type, "[%ld/%ld", &ifc_metric, &ifc_thresh );
ifc_type = 0;
if( strstr( type, "tunnel" ) != NULL )
ifc_type |= TUNNEL;
if( strstr( type, "querier" ) != NULL )
ifc_type |= QUERIER;
if( strstr( type, "down" ) != NULL )
ifc_type |= DOWN;
if( strstr( type, "disabled" ) != NULL )
ifc_type |= DISABLED;
if( strstr( type, "srcrt" ) != NULL)
ifc_type |= SRCRT;
if( strstr( type, "suspect" ) != NULL || suspect == TRUE )
ifc_type |= SUSPECT;
/*
** If the other end of this edge is not on the same subnet
** as this interface, assume it is a tunnel even if it wasn't
** explicitly marked as a tunnel.
*/
ht_entry_p = lookup_htable( &net->name_map, to_name );
if( ht_entry_p == NULL )
{
printf( "Invalid interface specified %s\n", to_name );
return NULL;
}
to_sub = (Interface *)ht_entry_p->subnet;
if( to_sub == NULL )
mask = 0xffffffff;
else
mask = to_sub->mask;
inet_parse( to_name, &to_addr, NULL );
inet_parse( frm_name, &frm_addr, NULL );
if( !(ifc_type & TUNNEL) && !((frm_addr & mask)
== (to_addr & mask)))
{
ifc_type |= ASSUMED;
ifc_type |= TUNNEL;
}
if( ifc_type & TUNNEL )
{
temp_ifc = find_ifc( net, NULL, frm_name, to_name );
if( temp_ifc != NULL )
{/*
** This tunnel already exists but before returning
** mark it as no longer suspect or down if this call
** did not mark it.
*/
if( !suspect )
temp_ifc->type &= ~SUSPECT;
if( !(ifc_type & (DOWN | DISABLED)))
temp_ifc->type &= ~(DOWN | DISABLED );
return NULL;
}
else
{
/* This edge is a tunnel so allocate a new interface
** because the first interface with this
** address is always the subnet interface.
*/
new_ifc = (Interface *)calloc( 1, sizeof( Interface ));
strcpy( new_ifc->name, frm_name );
new_ifc->address = frm_addr;
new_ifc->mask = 0xffffffff;
strcpy( new_ifc->to_name, to_name);
new_ifc->to_node = ht_entry_p->index;
new_ifc->to_addr = to_addr;
ht_entry_p = lookup_htable( &net->name_map, frm_name );
if( ht_entry_p == NULL )
{
printf( "Invalid interface specified %s\n", frm_name );
return NULL;
}
/*printf( "adding ifc %s to %s, frm_node = %ld, to_node = %ld\n",
frm_name, to_name, ht_entry_p->index, new_ifc->to_node );*/
node1 = &(net->adj_list[ht_entry_p->index]);
insert_ifc( &(node1->interfaces), new_ifc );
node1->degree++;
}
}
else
{/*
** This is a subnet connection so if the edge is already there
** to the subnet then we don't need this one. Just set the
** metric and threshold.
*/
new_ifc = find_ifc( net, NULL, frm_name, to_sub->name );
if( new_ifc == NULL )
{
new_ifc = (Interface *)calloc( 1, sizeof( Interface ));
strcpy( new_ifc->name, frm_name );
new_ifc->address = frm_addr;
new_ifc->mask = to_sub->mask;
strcpy( new_ifc->to_name, to_name);
ht_entry_p = lookup_htable( &net->name_map, to_name );
new_ifc->to_node = ht_entry_p->index;
new_ifc->to_addr = to_addr;
ht_entry_p = lookup_htable( &net->name_map, frm_name );
if( ht_entry_p == NULL )
{
printf( "Invalid interface specified %s\n", frm_name );
return NULL;
}
node1 = &(net->adj_list[ht_entry_p->index]);
/*
** Only mark the edges going into the subnet node as
** subnet interfaces.
*/
if( !(node1->type & SUBNET ))
ifc_type |= SUBNET;
insert_ifc( &(node1->interfaces), new_ifc );
node1->degree++;
}
if( !suspect )
new_ifc->type &= ~SUSPECT;
}
new_ifc->type |= ifc_type;
new_ifc->metric = ifc_metric;
new_ifc->threshold = ifc_thresh;
return new_ifc;
}
/*********************************************************************
FUNCTION: add_new_node()
DESCRIPTION:
This function is called whenever a new previously unknown
interface name is specified by the user for addition to the
network.
***********************************************************************/
int add_new_node( Network *net, NAME new_name, Ifc_list *subnets )
{
int args, index;
Interface *cur_ifc;
char cur_input[MAXLINE];
char ans;
NAME equiv_name, new_ip_name;
HENTRY_t *ht_entry_p;
printf( "Add interface %s (y/n)? ", new_name);
gets( cur_input );
sscanf( cur_input, "%c", &ans );
if( ans == 'n' )
return FALSE;
printf( "At an existing router? If so, enter equivalent interface: ");
gets( cur_input );
args = sscanf( cur_input, "%s", &equiv_name );
ht_entry_p = NULL;
if( args == 1 )
ht_entry_p = find_actual_name( net, equiv_name, subnets );
if( ht_entry_p != NULL )
{
index = ht_entry_p->index;
}
else
{
if( net->no_alloc <= net->no_nodes )
{
if( verbose )
printf( "\nNo more room in network for new nodes, rerun mrdebug with -a option\n");
return FALSE;
}
index = net->no_nodes;
net->no_nodes++;
}
cur_ifc = find_subnet( new_name, subnets );
insert_htable( &net->name_map, new_name, index, (long *)cur_ifc,
NULL );
if( find_ip_name( new_name, new_ip_name ))
insert_htable( &net->ip_map, new_ip_name, index, (long *)cur_ifc,
new_name );
if( cur_ifc != NULL )
{
/* Add the edge to the subnet node */
add_ifc( net, new_name, cur_ifc->name, "[1/1/suspect]", TRUE );
ht_entry_p = lookup_htable( &net->name_map, cur_ifc->name );
add_ifc( net, cur_ifc->name, new_name, "[0/0]", FALSE);
}
return TRUE;
}