#if HAVE_CONFIG_H #include #endif /* expects input to be in one of these formats: * "Status codes: s suppressed, d damped, h history, * valid, > best, i - internal" * "Origin codes: i - IGP, e - EGP, ? - incomplete" * "" * " Network Next Hop Metric LocPrf Weight Path" * "* 1.0.0.0 192.41.177.235 5 99 0 174 i" * "*>i 204.70.7.53 5 100 0 174 i" * "* 4.20.0.0/18 192.41.177.190 150 99 0 1849 i" * " h 5.20.0.0 192.41.177.190 150 99 0 1849 i" * "*>i 204.70.7.53 5 100 0 174 i" * " s 5.21.0.0 192.41.177.190 150 99 0 1849 i" * "*>i 204.70.7.53 5 100 0 174 i" * " d 5.22.0.0 192.41.177.190 150 99 0 1849 i" * "*>i 204.70.7.53 5 100 0 174 i" * * where the leading star indicates a non-heading line * except for history, suppressed, or dampened routes, * which are identified by all of the first 3 columns * and the ">" in 2nd column means this is a preferred route * and fields are always separated from each other by at least one space * and lines without a destination IP address use IP from closest line above * and the dest IP field always starts at the 4th char of a line * and the dest IP field is padded with spaces on right to 16 characters, * but can get as long as 18 with "255.255.255.255/32", * and the nexthop IP field is padded with spaces on right to 16 characters * * if the IP field has no mask bit count specified, * we are expected to use class-full (A, B, C, D, or E) * interpretation of the IP address itself (i.e. based * on the upper bits) * * * * alternate input format for destination IP addresses: * "*>i000011101010 192.41.177.235 5 99 0 174 i" * * where the destination IP address is represented in binary, * and the number of digits given indicates mask length * and the field is always padded on the right to exactly 32 characters * and all other fields are the same as above * * * * assumes that AS path always has a 2-character trailer * like " i" or " ?" or " e" * * assumes that AS numbers are always nonzero * * * * the first number in the AS path is the organization that * handed us the route, i.e. UUNet or SprintLink or ANS * * the last number in the AS path is the source AS, * i.e. the AS who owns the subnet talked about * * when there is only one number in the AS path, the route is * owned by that AS and was advertized directly to us * * when there are no numbers in the AS field, the route is * assumed to have originated within your network, which means * use your own AS number (145 for NSF vBNS, 3561 for MCI BIPP) * * a set of AS numbers whose subnets have been aggregated * into a single route by a third party (the AS appearing * to the left of them in the AS path string) will appear * like "{1325,3672,1681}" * * * * ftp://ftp.isi.edu/in-notes/iana/assignments/as-numbers * AS number 0 is reserved * AS numbers 1 to 32767 are assigned by the IANA * AS numbers 32768 to 64511 are reserved * AS numbers 64512 to 65534 are reserved * AS number 65535 is reserved * * * * calls InsertSubnet() for each parsed line */ /* conditional compile switches */ #define READBGP_TALKS FALSE #define READBGP_PARANOIA TRUE #define READBGP_DEBUG_PARSE FALSE #define READBGP_DEBUG_PARSE_AS FALSE #define READBGP_DEBUG_QSORT FALSE #define READBGP_DEBUG_INSERT FALSE #define READBGP_SHOWS_MEM_USE TRUE #define READBGP_SHOWS_DEF_AS TRUE #define READBGP_SHOWS_SKIP_AS TRUE #define READBGP_SHOWS_AGGREGS TRUE #define READBGP_WALKS FALSE #define READBGP_STRIPS_CR TRUE #define READBGP_STRIPS_LF TRUE #define READBGP_IGNORES_NONPREF TRUE #define READBGP_INPUTS_BINARY FALSE #define READBGP_SHOWS_PROGRESS TRUE #define READBGP_HAS_MAIN FALSE #define READBGP_SHOWS_TIMING TRUE #define READBGP_SORTS_SUBNETS FALSE #define READBGP_SHOWS_SORTING TRUE #define READBGP_SHOWS_POSTSORT FALSE #include /* printf() fprintf() gets() sscanf() */ #include /* atoi() getenv() min() */ #include /* strcpy() strchr() strlen() */ #include /* errno _sys_errlist */ #ifdef __unix__ #define min(a,b) (((a) < (b)) ? (a) : (b)) #define _sys_errlist sys_errlist #if !defined(ALPHA) && !defined(IRIX) && !defined(NETBSD) extern const char *const sys_errlist[]; #endif #endif #include "../types/types.h" #include "../integrat/subnet.h" /* InitSubnet() InsertSubnet() */ #include "../integrat/readbgp.h" /* our own prototypes and error messages */ #include "../wattcp/tcp.h" /* inet_ntoa() */ #include "../integrat/constant.h" /* DO_FOREGROUND_STATS */ #if !FLAT_MEM /* Not building NeTraMet using flat memory */ # define FLAT_USES_MALLOC TRUE #endif #include "../dpmi32/flat.h" /* flat_alloc() flat_remaining() */ #include "../integrat/dostats.h" /* nonzero() */ #ifndef __unix__ #include "../intel/byteswap.h" /* htonl() */ #endif /* none of this code gets compiled in * if it's isn't going to be called */ #if DO_FOREGROUND_STATS /* manifest constants */ #define MAX_USED_BGP_LINES min( (Bit32)100000, (Bit32)MAX_TREE_LEAVES ) #define NEXTHOP_IP_WIDTH (sizeof("255.255.255.255")-1) #if READBGP_INPUTS_BINARY # define MAX_TEXTLINE_SIZE 314 /* typically 104 */ # define MAX_DEST_IP_WIDTH 32 # define DEF_DEST_IP_WIDTH MAX_DEST_IP_WIDTH # define DEF_NEXTHOP_IP_OFFSET 36 # define DEF_AS_PATH_OFFSET 75 #else # define MAX_TEXTLINE_SIZE 300 /* typically 90 */ # define MAX_DEST_IP_WIDTH (sizeof("255.255.255.255/32")-1) # define DEF_DEST_IP_WIDTH (sizeof("255.255.255.0/32")-1) # define NEXTHOP_IP_WIDTH (sizeof("255.255.255.255")-1) # define DEF_NEXTHOP_IP_OFFSET 20 # define DEF_AS_PATH_OFFSET 59 #endif static char *aggregate_as_expansions[ AGGREGATE_AS_COUNT ]; static unsigned aggregate_as_actual = 0; static mask_from_length[ 33 ]; /* host byte order */ static unsigned length_from_high_nibble[ 16 ]; static unsigned as_path_memory_usage = 0; static unsigned subnet_parm_count = 0; static unsigned line = 0; static Bit16 default_as; static char *skipped_as; static unsigned skipped_as_length; static int skipped_as_eq_default_as; static Subnet *all_subnets = NULL; #if READBGP_DEBUG_PARSE_AS static unsigned parse_stopas = 52; #endif #if READBGP_DEBUG_PARSE static unsigned parse_stopline = 7000; #endif #if READBGP_DEBUG_QSORT static unsigned qsort_stopline = 48350; #endif #if READBGP_DEBUG_INSERT static unsigned insert_stopline = 30071; #endif /* readonly access to the array in this module * * accepts a number from 0 to 32, inclusive * * returned value is in host byte order */ Bit32 get_mask_from_length( unsigned length ) { if( length > 32 ) return 0; return mask_from_length[ length ]; } /* sets up global variables used when parsing BGP files */ static int init_bgp( void ) { unsigned count; unsigned mask; char *default_as_string; int default_as_integer; /* if we have ever been called, no need to init again */ if( all_subnets ) return 0; /* allocate memory for all the subnet parameters we will ever need */ all_subnets = (Subnet *) flat_alloc( MAX_USED_BGP_LINES * sizeof( Subnet ) ); if( all_subnets == NULL ) { fprintf( stderr, "init_bgp(): error %d '%s' allocating %d bytes for %d" " subnet parameter nodes\n", errno, _sys_errlist[errno], MAX_USED_BGP_LINES * sizeof( Subnet ), MAX_USED_BGP_LINES ); return ERROR_READBGP_ALLOC_SUBNET; } /* tell the subnet finding module the base address of our array */ SetSubnetExternalBase( all_subnets ); /* get a pointer to the string for the environment variable * that holds the default AS */ default_as_string = getenv( DEFAULT_AS_ENVAR ); if( default_as_string == NULL ) { fprintf( stderr, "init_bgp() error: environment variable '%s' is not set\n", DEFAULT_AS_ENVAR ); return ERROR_READBGP_NO_ENVAR; } /* convert the string to a short integer */ default_as_integer = atoi( default_as_string ); if( default_as_integer == 0 ) { fprintf( stderr, "init_bgp() error: cannot convert environment variable '%s'" " contents '%s' to integer\n", DEFAULT_AS_ENVAR, default_as_string ); return ERROR_READBGP_CANNOT_CVT_ENVAR; } /* check that the integer is in the proper range for an AS number */ if( default_as_integerNORMAL_AS_MAX ) { fprintf( stderr, "init_bgp() error: environment variable '%s' contents" " %d are not in the range %d through %d\n", DEFAULT_AS_ENVAR, default_as_integer, NORMAL_AS_BASE, NORMAL_AS_MAX ); return ERROR_READBGP_BAD_ENVAR_VALUE; } /* now finally assign default AS to the global variable */ default_as = default_as_integer; #if READBGP_SHOWS_DEF_AS printf( "bgp_init() setting default AS to %u\n", default_as ); #endif /* get a pointer to the string for the environment variable * that holds the string to skip on the beginning of AS path * before parsing exit AS */ skipped_as = getenv( SKIPPED_AS_ENVAR ); if( skipped_as != NULL ) { skipped_as_length = strlen( skipped_as ); skipped_as_eq_default_as = !strcmp( skipped_as, default_as_string ); } else { skipped_as = "(environment variable " SKIPPED_AS_ENVAR " not set)"; skipped_as_length = 0; skipped_as_eq_default_as = FALSE; } /* should I check all the AS numbers in the string for valid values??? * * if so, what about aggregates??? */ #if READBGP_SHOWS_SKIP_AS printf( "bgp_init() skipping '%s' before exit AS\n", skipped_as ); #endif /* fill in the table that maps from * high nibble to mask bit count */ for( count=0; count<16; count++ ) if( (count & 8) == 0 ) /* class A */ length_from_high_nibble[ count ] = 8; else if( (count & 4) == 0 ) /* class B */ length_from_high_nibble[ count ] = 16; else if( (count & 2) == 0 ) /* class C */ length_from_high_nibble[ count ] = 24; else if( (count & 1) == 0 ) /* class D (multicast) */ length_from_high_nibble[ count ] = 32; else /* class E (reserved) */ length_from_high_nibble[ count ] = 999; /* fill in the table that maps from * mask bit count to mask word * * need more than 1 statement so gdb (GNU debugger) * will be able to single-step * * note that on DEC alpha with OSF/1 compiler, * shifting an unsigned integer right will preserve * the high (sign) bit, but we do not depend on that * (nonportable, buggy) behavior */ mask_from_length[ 0 ] = 0; for( count=1,mask=1<<31; count<33; count++,mask=mask|mask>>1 ) { mask_from_length[ count ] = mask; mask = mask; } /* successful! */ return 0; } static Bit16 parse_as_number( char **string0, const char *as_path, const int is_src_as ) { Bit16 number; char *string = *string0; /* now convert from string to numeric * * assumes sizeof(int) > sizeof(Bit16) * * if not, use sscanf(string,"%u",&number) */ number = atoi( string ); #if READBGP_DEBUG_PARSE_AS if( number == parse_stopas ) printf( "debugger wants to stop here\n" ); #endif /* if the conversion succeeded, we are done */ if( number != 0 ) return number; /* if the first character is not an open curly brace... */ if( *string != '{' ) { #if READBGP_PARANOIA /* if this is exit AS and we didn't skip any, * or this is source AS, we should have gotten * a nonzero value */ if( is_src_as || skipped_as_length==0 ) { fprintf( stderr, "parse_as_number(%d) warning: %s AS '%s'" " in AS path '%s' should not be 0\n", line, is_src_as ? "source" : "exit", string, as_path ); number = default_as; } #endif return number; } /* if there is no fake AS we can assign... */ if( aggregate_as_actual >= AGGREGATE_AS_COUNT ) { fprintf( stderr, "parse_as_number(%d) error: no room for fake" " AS# for '%s' (already have %d); using default %d\n", line, string, aggregate_as_actual, default_as ); return default_as; } /* assign a fake AS number to this aggregation * * note that no attempt is made to merge multiple * occurrences of the same AS aggregation into the * same fake AS, since there are fewer than 30 of * them in the entire 95000 line BIPP routing table, * and it wouldn't be a big savings */ number = AGGREGATE_AS_BASE + aggregate_as_actual; aggregate_as_actual++; /* now we want to back up the pointer to the source * AS string, so it includes the aggregating AS # */ /* if we aren't using the beginning of the AS path... * * (if there is a space character before the source AS) */ if( string > as_path ) { /* back up 2 chars onto last character of previous AS * and keep going backwards until we hit the beginning * that AS, as indicated by hitting the beginning of * AS path as a whole or by hitting another space */ for( string-=2; string>as_path; string-- ) if( *string == ' ' ) { string++; break; } } *string0 = string; #if READBGP_SHOWS_AGGREGS fprintf( stdout, "assigning fake AS %d to aggregate '%s'\n", number, string ); #endif return number; } static int parse_bgp_line( char *buffer, unsigned length ) { char *preferred = buffer + 1; char *dest = buffer + 3; char *nexthop_addr_string = buffer + DEF_NEXTHOP_IP_OFFSET; char *as_path; char *src_as_string; char *exit_as_string; int nexthop_width; int converted; boolean result; unsigned count; unsigned mask_count; unsigned as_path_offset = DEF_AS_PATH_OFFSET; int as_path_width; unsigned addr_octets[ 4 ]; static Bit32 mask = 0; /* host byte order */ static Bit32 addr = 0; Bit32 nexthop_addr; Bit16 src_as; Bit16 exit_as; Subnet *parms; #if READBGP_INPUTS_BINARY char addr_binary[ MAX_DEST_IP_WIDTH + 1 ]; #else char trashed_for_dest; int dest_width; #endif /* if the route isn't valid, and it also isn't * history, suppressed, or dampened... */ if( buffer[0] != '*' && ( buffer[0] != ' ' || buffer[2] != ' ' || (buffer[1] != 'h' && buffer[1] != 'd' && buffer[1] != 's'))) /* ignore this input line */ return 0; /* if there is a destination IP address... */ if( dest[0] != ' ' ) { #if READBGP_INPUTS_BINARY /* try to read the destination IP address * * also remember how many characters the field required */ converted = sscanf( dest, "%s%n", addr_binary, &mask_count ); #if READBGP_PARANOIA /* make sure we got the IP address * * since we already checked (above) that the first character * of destination IP address is not space, this is really * a paranoia check of malformed addresses */ if( converted != 1 ) { fprintf( stderr, "warning on line %d: could not extract dest IP address '%s'\n", line, dest ); return 0; } #endif /* if we don't have enough bits to fill the word... */ if( mask_count < MAX_DEST_IP_WIDTH ) /* add the trailing zeroes so this field converts properly */ sprintf( addr_binary+mask_count, "%0*d", MAX_DEST_IP_WIDTH-mask_count, 0 ); /* now convert the ASCII string to an integer */ addr = strtoul( addr_binary, NULL, 2 ); #if READBGP_PARANOIA /* make sure the conversion worked * * note that strtoul() returns -1 when there are too many binary * digits, not the zero that the Borland documentation says it * will, and certainly not the value it would get with just the * first 32 bits, so we take pains to prevent that above */ if( addr == 0 ) { fprintf( stderr, "warning on line %d: dest IP address '%s' converted as zero!\n", line, addr_binary ); return 0; } #endif #else /* make sure we don't misinterpret next hop IP address * as the destination IP address when destination IP * address is missing * * but remember what character we are trashing, so we * can restore it after parsing dest, so we can then * parse next hop router */ trashed_for_dest = dest[ MAX_DEST_IP_WIDTH ]; dest[ MAX_DEST_IP_WIDTH ] = '\0'; /* try to read the destination IP address and its mask width * * also remember how many characters the field required * * note that we grab count of characters parsed ("%n" in format * string) both before and after looking for the mask width, * in case mask width is not found */ converted = sscanf( dest, "%u.%u.%u.%u%n/%u%n", addr_octets, addr_octets+1, addr_octets+2, addr_octets+3, &dest_width, &mask_count, &dest_width ); #if READBGP_PARANOIA /* make sure we got at least the IP address * * since we already checked (above) that the first character * of destination IP address is not space, this is really * a paranoia check of malformed or addresses */ if( converted < 4 ) { fprintf( stderr, "warning on line %d: skipping malformed dest IP address '%s'\n", line, dest ); return 0; } #endif /* make sure that the 4 pieces of the IP address * are each in the range 0 to 255 */ addr = 0; for( count=0; count<4; count++ ) #if READBGP_PARANOIA if( addr_octets[count] > 255 ) { fprintf( stderr, "error on line %d: byte %d >255\n", line, count ); return ERROR_READBGP_OCTET_TOO_BIG; } else #endif addr = (addr << 8) | addr_octets[count]; /* if the mask bit count was specified... */ if( converted == 5 ) { /* make sure the mask bit count is in the range 0 to 32 */ if( mask_count > 32 ) { fprintf( stderr, "error on line %d: mask bit count >32\n", line ); return ERROR_READBGP_MASK_TOO_BIG; } } else { /* derive mask bit count from the class lookup table */ mask_count = length_from_high_nibble[ (addr_octets[ 0 ] >> 4) & 15 ]; if( mask_count > 32 ) { fprintf( stderr, "error on line %d: cannot determine mask bit count; possible class E address\n", line ); return ERROR_READBGP_MASK_UNKNOWN; } } /* restore the character we nulled to terminate dest IP address */ dest[ MAX_DEST_IP_WIDTH ] = trashed_for_dest; /* if the destination IP address was wider than the default... */ if( dest_width > DEF_DEST_IP_WIDTH ) { /* adjust AS path offset to compensate for longer dest IP address */ as_path_offset += dest_width - DEF_DEST_IP_WIDTH; /* same for nexthop IP address */ nexthop_addr_string += dest_width - DEF_DEST_IP_WIDTH; } #endif /* look up the mask from its bit count */ mask = mask_from_length[ mask_count ]; } #if READBGP_IGNORES_NONPREF /* ignore the line if this is not a preferred route */ if( *preferred != '>' ) return 0; #endif /* make sure we don't misinterpret metric or locpref * as the nexthop IP address when nexthop IP address * is missing */ nexthop_addr_string[ NEXTHOP_IP_WIDTH ] = '\0'; /* try to read the nexthop IP address * * also remember how many characters the field required */ converted = sscanf( nexthop_addr_string, "%u.%u.%u.%u%n", addr_octets, addr_octets+1, addr_octets+2, addr_octets+3, &nexthop_width ); nexthop_addr = 0; /* make sure we got the IP address * * I have no clue when or why the nexthop IP address * might be blank, so this error is for discovery */ if( converted != 4 ) { fprintf( stderr, "warning on line %d: using 0.0.0.0 for malformed nexthop IP address '%s'\n", line, nexthop_addr_string ); } else { /* make sure that the 4 pieces of the nexthop IP address * are each in the range 0 to 255 */ for( count=0; count<4; count++ ) #if READBGP_PARANOIA if( addr_octets[count] > 255 ) { fprintf( stderr, "error on line %d: nexthop byte %d >255\n", line, count ); return ERROR_READBGP_OCTET_TOO_BIG; } else #endif nexthop_addr = (nexthop_addr << 8) | addr_octets[count]; } /* if the nexthop IP address was wider than we expected... */ if( nexthop_width > NEXTHOP_IP_WIDTH ) { /* this is an internal error! */ fprintf( stderr, "internal error on line %d: nexthop IP address '%s' length %d was longer than expected %d\n", line, nexthop_width, NEXTHOP_IP_WIDTH ); } as_path = buffer + as_path_offset; as_path_width = length - as_path_offset; /* if there isn't room for a digit, a space character * and an attribute, there aren't any numbers in the * AS path... */ if( as_path_width < 3 ) { /* if they wanted to skip some of the exit AS, * and the skipped AS string wasn't the same as default AS, * there is no way it could match now, so give up on this line */ if( skipped_as_length && !skipped_as_eq_default_as ) return 0; src_as = default_as; exit_as = default_as; as_path_width = 0; as_path[as_path_width] = '\0'; } else { /* extract the last (source) AS number from AS path */ /* strip the trailing attribute off the AS path */ as_path_width -= 2; as_path[as_path_width] = '\0'; /* if there isn't another space character embedded in AS path... */ src_as_string = strrchr( as_path, ' ' ); if( !src_as_string ) /* use the beginning of the AS path */ src_as_string = as_path; else /* the digits start after the space */ src_as_string++; src_as = parse_as_number( &src_as_string, as_path, TRUE ); /* also extract the first (exit) AS number from AS path */ if( skipped_as_length ) { /* if the beginning of the AS path doesn't match the prefix, * give up on the line */ if( strncmp( as_path, skipped_as, skipped_as_length ) ) return 0; exit_as_string = as_path + skipped_as_length; } else exit_as_string = as_path; exit_as = parse_as_number( &exit_as_string, as_path, FALSE ); } #if READBGP_PARANOIA count = strlen( as_path ); if( count != as_path_width ) { printf( "internal error: calculated width of AS path string '%s' is %d, but strlen() says %d\n", as_path, as_path_width, count ); } #endif #if READBGP_TALKS /* spit output */ printf( "line=%d subnet=%s mask=0x%.8X nexthop=%s exit_as=%d src_as=%d as_path='%s'\n", line, inet_ntoa(buffer+NEXTHOP_IP_WIDTH, addr), mask, inet_ntoa(buffer, nexthop_addr), exit_as, src_as, as_path ); #endif #if READBGP_DEBUG_PARSE /* do the conditional so the debugger doesn't * have to interpret it, 10X faster */ if( line == parse_stopline ) printf( "debugger wants to stop here\n" ); #endif /* allocate space and copy the dest IP address and mask into it */ if( subnet_parm_count >= MAX_USED_BGP_LINES ) { if( src_as >= AGGREGATE_AS_BASE ) aggregate_as_actual--; fprintf( stderr, "parse_bgp_line: error suballocating %d bytes for subnet structure; line=%d %s/%d exit_as=%d src_as=%d as_path='%s'\n", sizeof(Subnet), line, inet_ntoa(buffer,addr), bits_in_mask(htonl(mask)), exit_as, src_as, as_path ); return ERROR_READBGP_SUBALLOC_SUBNET; } parms = all_subnets + subnet_parm_count; subnet_parm_count++; parms->addr = htonl( addr ); parms->mask = htonl( mask ); parms->line = line; parms->src_as = src_as; parms->exit_as = exit_as; parms->nexthop_addr = nexthop_addr; /* allocate space and copy the AS path into it * * remember to leave room for the terminating NUL */ parms->as_path = (char *) flat_alloc( as_path_width + 1 ); if( !parms->as_path ) { subnet_parm_count--; if( src_as >= AGGREGATE_AS_BASE ) aggregate_as_actual--; if( exit_as >= AGGREGATE_AS_BASE ) aggregate_as_actual--; fprintf( stderr, "parse_bgp_line: error %d '%s' flat_alloc'ing %d bytes for as_path in subnet structure; line=%d addr=%s mask=0x%.8X as_path='%s'\n", errno, _sys_errlist[errno], as_path_width+1, line, inet_ntoa(buffer,addr), mask, as_path ); return ERROR_READBGP_ALLOC_AS_PATH; } as_path_memory_usage += as_path_width + 1; strcpy( parms->as_path, as_path ); if( src_as >= AGGREGATE_AS_BASE ) aggregate_as_expansions[ src_as - AGGREGATE_AS_BASE ] = parms->as_path + (src_as_string - as_path); if( exit_as >= AGGREGATE_AS_BASE ) aggregate_as_expansions[ exit_as - AGGREGATE_AS_BASE ] = parms->as_path + (exit_as_string - as_path); return 0; } #if READBGP_SORTS_SUBNETS /* called by qsort() */ static int _USERENTRY compare_subnets( const void *left0, const void *right0 ) { Subnet *left = (Subnet *) left0; Subnet *right = (Subnet *) right0; unsigned left_mask_length = bits_in_mask( left->mask ); unsigned right_mask_length = bits_in_mask( right->mask ); Bit32 left_addr, right_addr; #if READBGP_SHOWS_SORTING static unsigned count; #endif #if READBGP_SHOWS_SORTING count++; if( !(count % 10000) ) fprintf( stderr, "\b\b\b\b\b\b\b\b%8d", count ); #if READBGP_DEBUG_QSORT if( count == qsort_stopline ) fprintf( stdout, "debugger wants to stop here\n" ); #endif #endif if( leftall_subnets+subnet_parm_count ) fprintf( stderr, "compare_subnets() error on line %d: left arg 0x%.8X" " is out of range 0x%.8X to 0x%.8X\n", count, left, all_subnets, all_subnets+subnet_parm_count ); if( rightall_subnets+subnet_parm_count ) fprintf( stderr, "compare_subnets() error on line %d: right arg 0x%.8X" " is out of range 0x%.8X to 0x%.8X\n", count, right, all_subnets, all_subnets+subnet_parm_count ); /* enforce whoever's mask is shorter on both addresses */ if( left_mask_length < right_mask_length ) { left_addr = left->addr & left->mask; right_addr = right->addr & left->mask; } else { left_addr = left->addr & right->mask; right_addr = right->addr & right->mask; } /* if the destination IP address is not the same after * enforcing the mask, sort by IP address */ if( left_addr != right_addr ) return ntohl( left_addr ) - ntohl( right_addr ); /* when the routes overlap, we want the general one * (fewer mask bits) to be presented to InsertSubnet() * first, so we say left is "less than" right */ if( left_mask_length < right_mask_length ) return -1; return 1; } #endif /* READBGP_SORTS_SUBNETS */ int read_bgp_file( const char *infile_name ) { char buffer[ MAX_TEXTLINE_SIZE ]; int result; /* successful by default */ int result2; FILE *infile; Subnet *parms; unsigned count; unsigned line_before = line; unsigned subnet_node_count_before = GetSubnetNodeCount(); unsigned subnet_parm_count_before = subnet_parm_count; unsigned as_path_memory_usage_before = as_path_memory_usage; unsigned aggregate_as_actual_before = aggregate_as_actual; #if READBGP_SHOWS_MEM_USE unsigned coreleft_before; #endif #if !defined(__unix__) && READBGP_SHOWS_TIMING && !NETRAMET PentiumClock before, after; double elapsed; #endif #if READBGP_SHOWS_MEM_USE /* remember how much memory was available * when this function started * * note: may only work with Borland C++ compiler */ coreleft_before = flat_remaining(); #endif result = init_bgp(); if( result != 0 ) { fprintf( stderr, "read_bgp_file(): error %d initializing BGP parsing\n", result ); return result; } /* try to open the file */ infile = fopen( infile_name, "rt" ); if( infile == NULL ) { fprintf( stderr, "readbgp: error %d '%s' opening file '%s'\n", errno, _sys_errlist[errno], infile_name ); return ERROR_READBGP_FILE_OPEN; } #if !defined(__unix__) && READBGP_SHOWS_TIMING && !NETRAMET /* remember when parsing started */ before.set(); #endif #if READBGP_SHOWS_PROGRESS /* print the beginning part of the status line, * so the user knows what phase we are in */ fprintf( stderr, "parsing BGP line %6d", 0 ); #endif /* as long as there is data... */ while( !result && fgets( buffer, MAX_TEXTLINE_SIZE, infile ) ) { line++; /* find out how long the text line is */ count = strlen( buffer ); #if READBGP_STRIPS_LF /* strip off the trailing newline, if any, * by replacing it by a terminating NUL */ if( buffer[ count - 1 ] == '\n' ) { buffer[ count - 1 ] = '\0'; count--; } #endif #if READBGP_STRIPS_CR /* also strip off any trailing carriage return, * the same way we did the newline above */ if( buffer[ count - 1 ] == '\r' ) { buffer[ count - 1 ] = '\0'; count--; } #endif #if READBGP_SHOWS_PROGRESS if( !(line % 1000) ) /* show the current line number on stderr */ fprintf( stderr, "\b\b\b\b\b\b%6d", line ); #endif result = parse_bgp_line( buffer, count ); } /* end for */ #if READBGP_SHOWS_PROGRESS /* show the last line number on stderr, * in case it wasn't an even multiple of 1000 */ fprintf( stderr, "\b\b\b\b\b\b%6d", line ); #endif #if !defined(__unix__) && READBGP_SHOWS_TIMING && !NETRAMET /* calculate elapsed parsing time */ after.set(); after -= before; elapsed = after.get_seconds(); fprintf( stdout, "\n" ); fprintf( stdout, "%g S elapsed during parsing, %g uS per line\n", elapsed, elapsed*1e6/line ); #endif #if READBGP_SORTS_SUBNETS #if READBGP_SHOWS_SORTING fprintf( stderr, "\nsort comparison count %8d", 0 ); #endif #if !defined(__unix__) && READBGP_SHOWS_TIMING /* remember when sorting started */ before.set(); #endif /* now sort the subnets so that we can be sure to insert * the more general ones first * * this only matters when SUBNET.C is compiled to use the * "direct" lookup method instead of a Patricia tree * * note that this is mostly the case for output from a Cisco * router's "show ip bgp" command, because it does a depth-first * traversal of its Patricia tree, but I have seen groups of * up to 3 routes right next to each other which are reversed */ qsort( all_subnets, subnet_parm_count, sizeof(Subnet), compare_subnets ); #if !defined(__unix__) && READBGP_SHOWS_TIMING /* calculate elapsed sorting time */ after.set(); #if READBGP_SHOWS_SORTING fprintf( stderr, "\n" ); #endif after -= before; elapsed = after.get_seconds(); fprintf( stdout, "%g mS elapsed during sorting, %g uS per subnet\n", elapsed*1e3, elapsed*1e6/subnet_parm_count ); #endif #endif /* READBGP_SORTS_SUBNETS */ #if !defined(__unix__) && READBGP_SHOWS_TIMING && !NETRAMET /* remember when insertion started */ before.set(); #endif /* for all the subnets we parsed... */ for( count=subnet_parm_count_before; countline ); #endif #if READBGP_DEBUG_INSERT /* do the conditional so the debugger doesn't * have to interpret it, 10X faster */ if( parms->line == insert_stopline ) printf( "debugger wants to stop here\n" ); #endif /* should I be making an attempt to swap adjacent lines * so more general routes get inserted first??? */ /* now try to add this puppy to the radix trie * * note that if that fails, we must free the storage * because the subnet module hasn't taken ownership * of the data structure */ result2 = InsertSubnet( parms ); if( result2 == FALSE ) { fprintf( stderr, "parse_bgp_line: error inserting in radix trie; line=%d dest=%s/%d as_path='%s'\n", parms->line, inet_ntoa(buffer,ntohl(parms->addr)), bits_in_mask(parms->mask), parms->as_path ); /* it would be a joke to try to clean up memory now, * since the application will probably exit and the * parser's context is long gone */ if( !result ) result = ERROR_READBGP_INSERT_SUBNET; break; } } #if READBGP_SHOWS_POSTSORT fprintf( stderr, "\n", parms->line ); #endif #if !defined(__unix__) && READBGP_SHOWS_TIMING && !NETRAMET /* calculate elapsed insertion time */ after.set(); after -= before; elapsed = after.get_seconds(); fprintf( stdout, "%g mS elapsed during subnet insertion, %g uS per subnet\n", elapsed*1000, elapsed*1e6/nonzero(count) ); #endif /* show statistics for the parse and insert */ printf( "read_bgp_file( '%s' ) saw %d lines, %d radix trie nodes,\n" "\t%d subnet parameter nodes, and %d bytes of AS path strings\n" "\t and created %d fake AS numbers for aggregations\n", infile_name, line - line_before, GetSubnetNodeCount() - subnet_node_count_before, subnet_parm_count - subnet_parm_count_before, as_path_memory_usage - as_path_memory_usage_before, aggregate_as_actual - aggregate_as_actual_before ); #if READBGP_SHOWS_MEM_USE /* show memory usage of reading the BGP table */ printf( "read_bgp_file( '%s' ) asked for %d bytes in %d calls\n" "\tto flat_alloc(), which actually used %d bytes\n", infile_name, (GetSubnetNodeCount() - subnet_node_count_before) * sizeof(SubnetTree) + (subnet_parm_count - subnet_parm_count_before) * sizeof(Subnet) + (as_path_memory_usage - as_path_memory_usage_before), (GetSubnetNodeCount() - subnet_node_count_before) + 2 * (subnet_parm_count - subnet_parm_count_before), coreleft_before - flat_remaining() ); printf( "the %d nodes of the radix trie itself asked for %d bytes\n", (GetSubnetNodeCount() - subnet_node_count_before), (GetSubnetNodeCount() - subnet_node_count_before) * sizeof(SubnetTree) ); #endif /* if the parse went OK * but file had an error... */ if( !result && ferror( infile ) ) { fprintf( stderr, "readbgp: error %d '%s' reading file '%s'\n", errno, _sys_errlist[errno], infile_name ); result = ERROR_READBGP_FILE_READ; } /* close the input file */ result2 = fclose( infile ); if( result2!=0 && result==0 ) { fprintf( stderr, "readbgp: error %d '%s' closing file '%s'\n", errno, _sys_errlist[errno], infile_name ); result = ERROR_READBGP_FILE_CLOSE; } return result; } /* subnet structures created by this module will use * line numbers 1 through N * * this function tells you what that N is */ unsigned get_bgp_line_count( void ) { return line; } /* returns a string containing the list of AS numbers * that were aggregated into this fake AS if it was * * otherwise retuns NULL */ const char *get_aggregate_as_expansion( unsigned short as_number ) { /* if this AS number isn't one have actually used for an aggregate... */ if( as_number < AGGREGATE_AS_BASE || as_number-AGGREGATE_AS_BASE+1 > aggregate_as_actual ) return NULL; return aggregate_as_expansions[ as_number - AGGREGATE_AS_BASE ]; } #if READBGP_HAS_MAIN #define DUMP_BUF_SIZE (2 * 1024 * 1024) /* 2 MB */ int main( int argc, char *argv[] ) { int result; unsigned count; char *dump_buf; if( argc!=2 || argv[1][0]==0 ) { printf( "usage: %s bgp-file-from-router\n", argv[0] ); return ERROR_READBGP_BAD_PARMS; } /* initialize access to flat memory */ flat_init(); /* initialize the subnet module */ InitSubnet(); result = read_bgp_file( argv[1] ); if( result ) return result; #if READBGP_WALKS dump_buf = (char *) flat_alloc( DUMP_BUF_SIZE ); if( !dump_buf ) { fprintf( stderr, "readbgp: cannot allocate %d byte dump buffer\n", DUMP_BUF_SIZE ); return ERROR_READBGP_ALLOC_DUMP; } count = PrintSubnets( dump_buf, DUMP_BUF_SIZE ); printf( "used %d bytes of %d subnet dump buffer\n", count, DUMP_BUF_SIZE ); printf( "dump buffer is:\n%s", dump_buf ); flat_free( dump_buf ); #endif /* now how do I free up all the subnet radix trie? * * I can't! */ return 0; } #endif #endif /* DO_FOREGROUND_STATS */