#if HAVE_CONFIG_H #include #endif /* root of radix trie */ static SubnetTree *subnet_root = NULL; /* does any lookup-method-specific initialization * * returns TRUE if successful, FALSE if failure */ boolean InitSubnet2( void ) { return TRUE; } /* assumes that spot is not NULL * * this is unaffected by how we number bits * * use this family of functions any time you traverse * the tree so that the decision about what "zero" and * "one" fields represent is encapsulated, and can change easily */ /* old (presumably slow) code was: * * static SubnetTree *NextSubnetTree( SubnetTree *spot, Bit32 addr ) * { * if( addr & spot->mask ) * return spot->one; * else * return spot->zero; * } */ /* even though this is a C macro, you still cannot use * it as an LVALUE (the left side of an assignment) * * a function returning a C++ reference would have worked */ #define NextSubnetTree(spot,addr) ((addr)&(spot)->mask) ? (spot)->one : (spot)->zero /* cannot have an else statement after an invocation * of this macro in your code, unless you put curly * braces around your invocation or omit the semicolon * after the call, because that semicolon looks like an * empty statement to the compiler */ #define NextSubnetTreeAssign1(spot,addr,this) \ { \ if( (addr)&((spot)->mask) ) \ (spot)->one = this; \ else \ (spot)->zero = this; \ } /* same problem with else statements as NextSubnetTreeAssign1() */ #define NextSubnetTreeAssign2(spot,addr,this,other) \ { \ if( (addr)&((spot)->mask) ) \ { \ (spot)->one = this; \ (spot)->zero = other; \ } \ else \ { \ (spot)->one = other; \ (spot)->zero = this; \ } \ } /* assumes that IP address passed is in network byte order */ static Subnet *FindSubnetRecurse( Bit32 address, SubnetTree *node ) { Bit32 mask; Subnet *is_child; if( !node ) return NULL; is_child = FindSubnetRecurse( address, NextSubnetTree( node, address ) ); if( is_child ) return is_child; if( !node->external ) return NULL; if( (address & node->external->mask) == node->external->addr ) return node->external; return NULL; } /* accepts address in network byte order * * returns pointer to routing information, * or NULL if no route can be found */ Subnet *FindSubnet( register Bit32 address ) { #if !defined(__unix__) && SUBNET_FIND_TIMING PentiumClock before; #endif Subnet *result; #if !defined(__unix__) && SUBNET_FIND_TIMING before.set(); #endif result = FindSubnetRecurse( address, subnet_root ); #if !defined(__unix__) && SUBNET_FIND_TIMING find_timing.set(); find_timing -= before; #endif return result; } /* assumes Subnet address and mask fields are in network byte order * * zero masks not allowed * * assumes memory pointed to by "external" argument * was allocated from heap and can be owned by us afterwards * * returns TRUE if successful, FALSE otherwise */ #pragma warn -par boolean DeleteSubnet( Subnet *external ) { return FALSE; // not implemented yet } #pragma warn .par /* assumes Subnet address and mask fields are in network byte order * * allows zero masks * * assumes memory pointed to by "external" argument * was allocated from heap and can be owned by us afterwards * * returns TRUE if successful, FALSE otherwise */ boolean InsertSubnet( Subnet *external ) { int bit, diff_bit; /* must be signed to allow host routes! */ Bit32 addr; SubnetTree *spot, *bottom_spot, *next_spot; SubnetTree *new_spot, *new_spot2; char temp[ 100 ]; /* so we can call inet_ntoa() */ /* make sure the caller does not have any bits set * in their address that are cleared in their mask * (enforce the mask) */ external->addr &= external->mask; /* point at the bit beyond (less significant than) * the least significant set bit of mask * * if no bits on in mask (default route), bit will * be 31 (most significant) * * if all bits on in mask (host route), bit will * be -1 (less than least significant) */ bit = lsb_of_long( external->mask ) - 1; /* keep track of how many subnets had this mask length */ subnets_per_mask_length[ MAX_ADDR_BITS - bit - 2 ]++; addr = external->addr; /* if there is nothing in the tree... */ if( !subnet_root ) { new_spot = (SubnetTree *) flat_alloc( sizeof( SubnetTree ) ); if( !new_spot ) return FALSE; subnet_node_count++; new_spot->zero = NULL; new_spot->one = NULL; new_spot->parent = NULL; /* this is root node */ new_spot->bit = bit; new_spot->mask = htonl( 1 << bit ); new_spot->external = external; subnet_root = new_spot; /* already done... amazing! */ return TRUE; } /* first look for a tree node which would test a less * significant bit, and which has external data attached * * note that less-significant bits are further from the * root node */ for( spot=subnet_root; ; spot=next_spot ) { next_spot = NextSubnetTree( spot, addr ); /* if this node tests the same or less significant * bit, and it has data attached, stop here */ if( (spot->bit <= bit) && spot->external ) break; /* if we would go nowhere from this split, * stop here */ if( !next_spot ) { /* consistency check */ if( !spot->external ) { printf( "subnet internal error: no child on our path," " but no external data is attached!\n" ); return FALSE; } /* we still do not know we will be inserting below * this guy, because if we differ from him at a more * significant bit than his mask length, we will want * to insert above him */ break; } } /* find out the most significant differing bit */ diff_bit = msb_of_long( addr ^ spot->external->addr ); /* if this node tests the same bit, * and IP address is the same, * it is a duplicate */ if( diff_bit==MAX_ADDR_BITS && bit==spot->bit ) { printf( "subnet %s 0x%X '%s' originally inserted by line %d found; new insertion" " '%s' from line %d ignored\n", inet_ntoa(temp,ntohl(external->addr)), ntohl(external->mask), spot->external->as_path, spot->external->line, external->as_path, external->line ); return TRUE; } /* if no bits differ which are common to both masks... */ if( diff_bit==MAX_ADDR_BITS || diff_bit<=bit || diff_bit<=spot->bit ) { /* the differences in mask length will determine * which routing takes precedence, so act as if * the first bit beyond our mask was different */ diff_bit = bit; } /* remember the bottom spot, in case we need its * data for comparison purposes later */ bottom_spot = spot; /* step back up the tree until we get to an old node * which is checking the same or more significant bit */ while( diff_bit > spot->bit ) { /* cannot go up above root node */ if( spot->parent == NULL ) break; spot = spot->parent; } /* if we are at root node, it must * test too insignificant a bit... */ if( diff_bit > spot->bit ) { /* consistency check */ if( spot != subnet_root ) { printf( "subnet internal error: node with no parent is not root!\n" ); exit( 1 ); } /* we must insert above current node, * becoming the new root node * * but we still don't know whether we will attach * external data here or on a new child node */ new_spot = (SubnetTree *) flat_alloc( sizeof( SubnetTree ) ); if( !new_spot ) return FALSE; subnet_node_count++; new_spot->zero = NULL; new_spot->one = NULL; new_spot->parent = NULL; /* this is root node */ new_spot->bit = diff_bit; new_spot->mask = htonl( 1 << diff_bit ); subnet_root = new_spot; /* reuse the code below that deals with 2nd nodes */ next_spot = spot; } /* if the old node is checking a more significant bit... */ else if( diff_bit < spot->bit ) { /* if there is a node below, it must be checking too * insignificant a bit, or we would have stopped there * * so we want to at least put a node below this one * * but we still don't know whether we will attach * external data here or on a new child node */ new_spot = (SubnetTree *) flat_alloc( sizeof( SubnetTree ) ); if( !new_spot ) return FALSE; subnet_node_count++; new_spot->zero = NULL; new_spot->one = NULL; new_spot->parent = spot; new_spot->bit = diff_bit; new_spot->mask = htonl( 1 << diff_bit ); /* it is safe to use our address here because * we are guaranteed that it is checking a bit * which is inside our mask */ next_spot = NextSubnetTree( spot, addr ); NextSubnetTreeAssign1( spot, addr, new_spot ); } /* old node must have been checking the bit we want */ else { /* old node should take the place of * the split we would have created */ new_spot = spot; /* it is safe to use our address here, because * we do not use next_spot below if diff_bit==bit */ next_spot = NextSubnetTree( spot, addr ); } /* now do we also have to insert a 2nd (child) node? * * not if the difference bit is outside one of the masks */ if( diff_bit == bit ) { if( new_spot == spot ) { /* consistency check */ if( spot->external ) { printf( "subnet internal error: old spot had exact bit we" " wanted (%d), and it was outside the new mask, but the" " external data was already filled in!\n", diff_bit ); return FALSE; } } else { /* we do not have the bit in our address * to compare; use the address we saw below */ NextSubnetTreeAssign1( new_spot, bottom_spot->external->addr, next_spot ); if( next_spot ) next_spot->parent = new_spot; } new_spot->external = external; } else { /* consistency check */ if( new_spot == spot ) if( next_spot ) { printf( "subnet internal error: old spot had exact bit we" " wanted (%d), and it was inside (%d) the new mask, but the" " next pointer was already filled in!\n", diff_bit, bit ); return FALSE; } new_spot2 = (SubnetTree *) flat_alloc( sizeof( SubnetTree ) ); if( !new_spot2 ) return FALSE; subnet_node_count++; new_spot2->zero = NULL; new_spot2->one = NULL; new_spot2->parent = new_spot; new_spot2->bit = bit; new_spot2->mask = htonl( 1 << bit ); new_spot2->external = external; if( new_spot == spot ) { /* we are overwriting next_spot in an existing split * to point at our new node */ /* safe to use our own address because we already * know that new_spot->bit is inside our mask * because diff_bit != bit */ NextSubnetTreeAssign1( new_spot, addr, new_spot2 ); } else { /* we are pointing a new split at a new node, * and pointing the other path at the old nodes */ new_spot->external = NULL; /* safe to use our own address because we already * know that new_spot->bit is inside our mask * because diff_bit != bit */ NextSubnetTreeAssign2( new_spot, addr, new_spot2, next_spot ); if( next_spot ) next_spot->parent = new_spot; } } /* done... finally! */ return TRUE; } /* calls a function for each node, in order of preference for routing */ static boolean WalkSubnetsRecurse( WalkSubnetFunction function, void *args, SubnetTree *node ) { if( !node ) return TRUE; /* give the user function a chance to look at the data * before we recurse deeper */ if( node->external ) if( !function( TRUE, node->external, args ) ) return FALSE; /* this (depth first, zero first) printout ordering of children * is arbitrary; actual routing lookup does not care */ if( !WalkSubnetsRecurse( function, args, NextSubnetTree( node, 0 ) ) ) return FALSE; if( !WalkSubnetsRecurse( function, args, NextSubnetTree( node, -1 ) ) ) return FALSE; /* give the user function a chance to look at the data * now that we are done recursing deeper */ if( node->external ) if( !function( FALSE, node->external, args ) ) return FALSE; return TRUE; } /* call a user-defined function once for each routing, * in order of preference * * returns TRUE if successful, FALSE if failure */ boolean WalkSubnets( WalkSubnetFunction function, void *args ) { if( !subnet_root ) return FALSE; return WalkSubnetsRecurse( function, args, (SubnetTree *)subnet_root ); } /* used for comparison of internal state with other implementations * of same algorithm for same data structures, or different inputs * * temporarily destroys the first word in each node or leaf, to know * whether it was visited yet */ void DumpRawSubnets( void ) { } void ShowSubnetStatistics( void ) { int count; fprintf( stdout, "\n" ); for( count=0; count