routing_table.c

/* Copyright 2008 Michael Marsh, University of Maryland.
 *
 * This file is part of pydtn.
 *
 * pydtn is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * pydtn 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 pydtn.  If not, see <http://www.gnu.org/licenses/>.
 *
 * The views and conclusions contained in the software and documentation
 * are those of the authors and should not be interpreted as representing
 * official policies, either expressed or implied, of the University
 * of Maryland.
 *
 * pydtn extends and embeds the Python interpreter, which is
 * Copyright 2001-2006 Python Software Foundation, All Rights Reserved,
 * and is released under the PSF License Agreement.
 *
 * RANLUX random number generation uses the Boost library,
 * Copyright 1994-2006 by various authors (details in individual files),
 * which is released under the Boost Software License, Version 1.0.
 */

#include "aodv.h"
#include <string.h>

void
clear_aodv_routing_table( aodv_routing_table_t* table )
{
   aodv_table_entry_t* head;
   aodv_table_entry_t* curr;
   aodv_table_entry_t* next;

   if ( NULL == table )
   {
      return;
   }
   if ( NULL == table->head )
   {
      return;
   }

   head = table->head;
   curr = head;
   do
   {
      next = curr->next;
      free_aodv_table_entry(curr);
      curr = next;
   } while ( curr != head );

   table->head = NULL;
}

aodv_table_entry_t*
add_aodv_table_entry( aodv_routing_table_t* table,
                      const aodv_addr_t* destination,
                      uint16_t prefix_size )
{
   aodv_table_entry_t* head;
   aodv_table_entry_t* tail;
   aodv_table_entry_t* temp;

   if ( NULL == table )
   {
      return NULL;
   }

   temp = new_aodv_table_entry();
   if ( NULL == temp )
   {
      return NULL;
   }
   set_aodv_addr( &(temp->destination.addr), destination );
   temp->destination.prefix = prefix_size;

   if ( NULL == table->head )
   {
      table->head = temp;
      temp->next = temp;
      temp->prev = temp;
   }
   else
   {
      head = table->head;
      tail = head->prev;
      temp->next = head;
      temp->prev = tail;
      head->prev = temp;
      tail->next = temp;
   }

   return temp;
}

void
remove_aodv_table_entry( aodv_routing_table_t* table,
                         aodv_table_entry_t* entry )
{
   aodv_table_entry_t* curr;
   aodv_table_entry_t* next;
   unsigned char is_head;
   unsigned char is_tail;

   if ( NULL == table ) return;
   if ( NULL == entry ) return;
   if ( NULL == table->head ) return;

   curr = table->head;
   do
   {
      next = curr->next;
      if ( curr == entry )
      {
         is_head = 0;
         is_tail = 0;
         if ( curr == table->head ) is_head = 1;
         if ( curr == table->head->prev ) is_tail = 1;

         if ( is_head && is_tail )
         {
            table->head = NULL;
            next = NULL;
         }
         else
         {
            if ( is_head )
            {
               table->head = next;
            }
            curr->prev->next = next;
            next->prev = curr->prev;
         }
         free_aodv_table_entry( curr );
         return;
      }
      curr = next;
   } while ( curr != table->head );
}

aodv_table_entry_t*
update_aodv_table_entry( aodv_state_t* state,
                         const aodv_msghdr_t* hdrs,
                         const aodv_node_list_t* node,
                         unsigned char hop_count )
{
   aodv_table_entry_t*  entry;
   uint32_t cmp;

   if ( NULL == state ) return NULL;
   if ( NULL == hdrs ) return NULL;
   if ( NULL == node ) return NULL;

   entry = aodv_lookup( &(state->routing_table), &(node->node) );
   if ( NULL == entry )
   {
      entry =
         add_aodv_table_entry( &(state->routing_table), &(node->node), 0 );
      if ( NULL == entry ) return NULL;
   }
   cmp = aodv_cmp_seq( node->seq, entry->dest_seq );
   if ( ( cmp > 0 ) ||
        ( ( 0 == cmp ) && ( ( ! entry->valid_route ) ||
                            ( hop_count < entry->hop_count ) ) ) )
   {
      aodv_update_route_expiry( state, entry );
      entry->dest_seq = node->seq;
      set_aodv_addr( &(entry->next_hop), &(hdrs->addr) );
      entry->hop_count = hop_count;
      entry->interface = hdrs->interface;
      entry->valid_route = 1;
   }
   return entry;
}

aodv_table_entry_t*
new_aodv_table_entry()
{
   aodv_table_entry_t* temp;
   temp = (aodv_table_entry_t*) malloc( sizeof(aodv_table_entry_t) );
   if ( NULL == temp )
   {
      return NULL;
   }
   temp->next                    = NULL;
   temp->prev                    = NULL;
   temp->destination.addr.data   = NULL;
   temp->destination.addr.length = 0U;
   temp->destination.prefix      = 0;
   temp->dest_seq                = 0;
   temp->next_hop.data           = NULL;
   temp->next_hop.length         = 0U;
   temp->lifetime.tv_sec         = -1;
   temp->lifetime.tv_usec        = 0;
   temp->hop_count               = 0;
   temp->interface               = -1;
   temp->valid_route             = 0;
   return temp;
}

void
free_aodv_table_entry( aodv_table_entry_t* entry )
{
   if ( NULL == entry ) return;
   if ( NULL != entry->destination.addr.data )
      free( entry->destination.addr.data );
   if ( NULL != entry->next_hop.data )
      free( entry->next_hop.data );
   free(entry);
}

/*
 * This is a horribly inefficient way to do lookups, but for the moment
 * we're using a regular linked list for the routing table, so we can't
 * really do too much better.  Ideally we'd have a better structure
 * for storing routing table entries.
 *
 */
aodv_table_entry_t*
aodv_lookup( const aodv_routing_table_t* table,
             const aodv_addr_t* destination )
{
   aodv_table_entry_t* curr;
   aodv_table_entry_t* best;
   uint16_t curr_prefix;
   uint16_t best_prefix;

   if ( NULL == table )
   {
      return NULL;
   }
   if ( NULL == table->head )
   {
      return NULL;
   }
   if ( NULL == destination )
   {
      return NULL;
   }

   best = NULL;
   best_prefix = ~0;
   curr = table->head;
   do
   {
      if ( 0 == curr->destination.prefix )
      {
         if ( 0 == aodv_cmp_addr( &(curr->destination.addr), destination ) )
         {
            return curr;
         }
      }
      else
      {
         /*
          * I believe this does what the previous version did.
          * That is, it starts with a longest-possible prefix
          * length.  It then looks at each entry, and if it
          * matches with a shorter prefix, then it takes the
          * new entry.
          *
          * Two things to note:
          *
          * 1) "prefix length" is inverted here relative to what
          *    we'd generally think of.  This is to conform with
          *    the terminology in the specification.  The length
          *    of the prefix is the number of bits that are masked.
          *    Consequently, a length-0 prefix has no bits masked, and
          *    the whole thing is relevant.
          *
          * 2) We need an additional check that the specified prefix
          *    is not longer than the destination's fully specified
          *    address.
          */
         curr_prefix = curr->destination.prefix;
         if ( (8 * destination->length) >= curr_prefix )
         {
            if ( curr_prefix < best_prefix )
            {
               char nomatch = 0;
               uint16_t ip = curr_prefix / 8;
               unsigned char bp = curr_prefix % 8;

               /*
                * General comment:
                *
                * We're using or-equal here because anything non-zero
                * or true will have a bit set somewhere, and or-equal
                * will never flip a bit from 1 to 0, only from 0 to 1.
                * That means something passing a (rejection) test will
                * set *something* to 1, and this will carry through
                * subsequent tests.
                */

               /* First check full-width bytes, if any. */
               if ( ip > 0 )
               {
                  nomatch |= memcmp( curr->destination.addr.data,
                                     destination->data,
                                     ip );
               }

               /* Now mask the bits in the final byte, if any. */
               if ( ( !nomatch ) && ( bp > 0 ) )
               {
                  unsigned char mask = ~0 << bp;
                  nomatch |= ( ( curr->destination.addr.data[ip] & mask ) !=
                               ( destination->data[ip] & mask ) );

               }

               if ( !nomatch )
               {
                  best = curr;
                  best_prefix = curr_prefix;
               }
            }
         }
      }
      curr = curr->next;
   } while ( curr != table->head );

   return best;
}

void
aodv_invalidate_route( aodv_state_t* state, const aodv_addr_t* destination )
{
   aodv_routing_table_t* table;
   aodv_table_entry_t* entry;

   if ( NULL == state ) return;

   table = &(state->routing_table);
   entry = aodv_lookup( table, destination );
   if ( NULL == entry )
   {
      return;
   }
   if ( entry->valid_route )
   {
      aodv_invalidate_routing_entry( state, entry );
   }
}

void
aodv_invalidate_routing_entry( aodv_state_t* state,
                               aodv_table_entry_t* entry )
{
   if ( NULL == state ) return;
   if ( NULL == entry ) return;

   entry->valid_route = 0;
   aodv_incr_seq_base( &(entry->dest_seq) );
}

unsigned char
aodv_table_entry_is_expired( const aodv_table_entry_t* entry )
{
   if ( NULL == entry ) return 0;

   return aodv_pasttime( &(entry->lifetime) );
}

static void
_update_route_lifetime( aodv_table_entry_t* entry,
                        unsigned int lifetime )
{
   struct timeval* tv = &(entry->lifetime);
   aodv_gettime(tv);
   tv->tv_usec += 1000 * lifetime;
   while( tv->tv_usec >= 1000000 )
   {
      tv->tv_usec -= 1000000;
      tv->tv_sec += 1;
   }
}

void
aodv_update_route_expiry( const aodv_state_t* state,
                          aodv_table_entry_t* entry )
{
   _update_route_lifetime( entry, state->params.active_route_timeout );
}

void
aodv_update_invalid_route_lifetime( const aodv_state_t* state,
                                    aodv_table_entry_t* entry )
{
   _update_route_lifetime( entry, state->params.delete_period );
}

void
aodv_broken_link( aodv_state_t* state, const aodv_addr_t* bad_hop )
{
   aodv_table_entry_t* thead;
   aodv_table_entry_t* tcurr;
   int gen_rerr = 0;
   aodv_rerr_t rerr;
   rerr.dest_count = 0;
   rerr.unreachable = 0;

   if ( NULL == state ) return;

   thead = state->routing_table.head;
   tcurr = thead;
   if ( 0 != thead )
   {
      do
      {
         if ( tcurr->valid_route &&
              ( 0 == aodv_cmp_addr( bad_hop, &(tcurr->next_hop) ) ) )
         {
            gen_rerr = 1;
            aodv_invalidate_routing_entry( state, tcurr );
            rerr.dest_count++;
            aodv_add_to_node_list( &(rerr.unreachable),
                                   &(tcurr->destination.addr),
                                   tcurr->dest_seq );
         }
         tcurr = tcurr->next;
      } while ( tcurr != thead );
   }

   if ( gen_rerr )
   {
      if ( aodv_insert_time( state->rerr_time_ring ) )
      {
         aodv_bcast_rerr( state, &rerr );
      }
   }
}

---