iproutingp.nc

tinyos-2.x.rar

/*
 * "Copyright (c) 2008 The Regents of the University  of California.
 * All rights reserved."
 *
 * Permission to use, copy, modify, and distribute this software and its
 * documentation for any purpose, without fee, and without written agreement is
 * hereby granted, provided that the above copyright notice, the following
 * two paragraphs and the author appear in all copies of this software.
 *
 * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
 * OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
 * CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
 * ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS."
 *
 */

#include "IPDispatch.h"
#include "PrintfUART.h"

module IPRoutingP {
  provides interface IPRouting;
  provides interface Statistics<route_statistics_t>;

  uses interface IPExtensions;
  uses interface TLVHeader as DestinationExt;
  uses interface ICMP;
  uses interface Boot;
  uses interface IPAddress;
  uses interface Random;

  uses interface Timer<TMilli> as SortTimer;

  uses interface IP as TGenSend;
  uses interface Timer<TMilli> as TrafficGenTimer;

  uses interface Leds;

} implementation {

#ifdef PRINTFUART_ENABLED
// #undef dbg
// #define dbg(X, fmt, args...)  printfUART(fmt, ## args)
#endif

  enum {
    SHORT_EPOCH = 0,
    LONG_EPOCH = 1,
  };

  //uint16_t current_epoch;
  //route_statistics_t stats;
  uint16_t last_qual;
  uint8_t last_hops;
  uint16_t reportSeqno;

  bool soliciting;

  // pointer into the neighbor table of the current entry that is our
  // first choice.
  struct neigh_entry *default_route;
  uint16_t default_route_failures;

  uint32_t traffic_interval;
  bool traffic_sent;

#ifdef CENTRALIZED_ROUTING
  // this is the routing table (k parents);
  struct flow_path full_path_entries[N_FULL_PATH_ENTRIES];
  struct flow_entry flow_table[N_FLOW_ENT];
#endif
  struct neigh_entry neigh_table[N_NEIGH];

  void printTable();
  error_t freeFullPath(struct flow_path* path);
  void updateFlowCounts(struct flow_entry *target);
  void updateRankings();
  void swapNodes(struct neigh_entry *highNode, struct neigh_entry *lowNode);
  uint8_t checkThresh(uint32_t firstVal, uint32_t secondVal, uint16_t thresh);
  void evictNeighbor(struct neigh_entry *neigh);
  uint16_t getMetric(struct neigh_entry *neigh);

  void clearStats(struct neigh_entry *r) {
    ip_memclr((uint8_t *)r->stats, sizeof(struct epoch_stats) * N_EPOCHS);
#if 0
    int j;
    for (j = 0; j < N_EPOCHS; j++) {
      r->stats[j].total   = 0;
      r->stats[j].success = 0;
      r->stats[j].receptions = 0;
    }
#endif
  }

  void clearEpoch(uint8_t target_epoch) {
    int i;
    for (i = 0; i < N_NEIGH; i++) {
      neigh_table[i].stats[target_epoch].total = 0;
      neigh_table[i].stats[target_epoch].success = 0;
      neigh_table[i].stats[target_epoch].receptions = 0;
    }
  }

  void restartTrafficGen() {
    traffic_interval = TGEN_BASE_TIME;
    // jitter the period by 10% to prevent synchronization
    traffic_interval += (call Random.rand16()) % (TGEN_BASE_TIME);
    if (call TrafficGenTimer.isRunning())
      call TrafficGenTimer.stop();
    traffic_sent = FALSE;

    call TrafficGenTimer.startOneShot(traffic_interval);
  }

  event void TrafficGenTimer.fired() {
    struct split_ip_msg *msg;
    if (traffic_sent) goto done;
    msg = (struct split_ip_msg *)ip_malloc(sizeof(struct split_ip_msg));
    if (msg == NULL) {
      printfUART("malloc fail\n");
      goto done;
    }
    traffic_sent = FALSE;

    ip_memclr((uint8_t *)&msg->hdr, sizeof(struct ip6_hdr));
    inet_pton6("ff05::1", &msg->hdr.ip6_dst);
    call IPAddress.getIPAddr(&msg->hdr.ip6_src);
    msg->data = NULL;
    msg->data_len = 0;
    msg->headers = NULL;

    dbg("IPRouting", "Sending generated message\n");
    call TGenSend.send(msg);
    ip_free(msg);
  done:
    // restart timer
    dbg("IPRouting", "Done checking for tgen\n");
    traffic_sent = FALSE;
    traffic_interval *= 2;
    if (traffic_interval > TGEN_MAX_INTERVAL)
      traffic_interval = TGEN_MAX_INTERVAL;
    call TrafficGenTimer.startOneShot(traffic_interval);
  }

  event void TGenSend.recv(struct ip6_hdr *iph,
                           void *payload, 
                           struct ip_metadata *meta) {

  }

  command void IPRouting.reset() {
    int i;

    for (i = 0; i < N_NEIGH; i++) {
      neigh_table[i].flags = 0;
      clearStats(&neigh_table[i]);
    }

#ifdef CENTRALIZED_ROUTING
    call IPRouting.clearFlows();
    for (i = 0; i < N_FULL_PATH_ENTRIES; i++) {
      full_path_entries[i].path_len = 0;
    }
#endif

    // current_epoch = 0;
    if (!soliciting) {
      call ICMP.sendSolicitations();
      soliciting = TRUE;
    }
    //reRouting = FALSE;
    default_route_failures = 0;
    default_route = &neigh_table[0];
    // boot with this true so the router will invalidate any state
    // associated from us when it gets the first packet.
    last_qual = 0xffff;
    last_hops = 0xff;

    traffic_sent = FALSE;
    restartTrafficGen();
  }

  event void Boot.booted() {
    call IPRouting.reset();
    reportSeqno = call Random.rand16();

    call Statistics.clear();
    call SortTimer.startPeriodic(1024L * 60);

  }
  
  command bool IPRouting.isForMe(struct ip6_hdr *hdr) {
    // the destination prefix is either link-local or global, or
    // multicast (we accept all multicast packets), and the suffix is
    // me.
    struct in6_addr *my_address = call IPAddress.getPublicAddr();
    return (((cmpPfx(my_address->s6_addr, hdr->ip6_dst.s6_addr) || 
              cmpPfx(linklocal_prefix, hdr->ip6_dst.s6_addr)) &&
             cmpPfx(&my_address->s6_addr[8], &hdr->ip6_dst.s6_addr[8])) ||
            (hdr->ip6_dst.s6_addr[0] == 0xff && 
             (hdr->ip6_dst.s6_addr[1] & 0x0f) <= 3))
;
  }

#ifdef CENTRALIZED_ROUTING
  void print_rinstall(struct rinstall_header *rih) {
    uint8_t i;
    dbg("Install", "rinstall header:\n");
    dbg_clear("Install", "\tnxt_header\t0x%x\n", rih->ext.nxt_hdr);
    dbg_clear("Install", "\tlen\t0x%x\n", rih->ext.len);
    dbg_clear("Install", "\tflags\t0x%x\n", rih->flags);
    dbg_clear("Install", "\tmatch_src\t0x%x\n", ntohs(rih->match.src));
    dbg_clear("Install", "\tmatch_prev\t0x%x\n", ntohs(rih->match.prev_hop));
    dbg_clear("Install", "\tmatch_dest\t0x%x\n", ntohs(rih->match.dest));
    dbg_clear("Install", "\tpath_len\t0x%x\n", rih->path_len);
    dbg_clear("Install", "\tcurrent\t0x%x\n", rih->current);
    for(i = 0; i < rih->path_len; i++)
      dbg_clear("Install", "\thop[%u]\t0x%x\n", i, ntohs(rih->path[i]));
  }

  struct flow_entry *getFlowEntry(cmpr_ip6_addr_t a) {
    int i;
    dbg("IPRouting", "getFlowEntry called for 0x%x\n", a);
    for (i = 0; i < N_FLOW_ENT; i++) {
      if (IS_VALID_SLOT(&flow_table[i]) && flow_table[i].match.dest == a) {
        dbg("IPRouting", "Match found in slot [%u]\n", i);
        return &(flow_table[i]);
      }
    }
    return NULL;
  }

  //  Add this extra layer of indirection to allow us to do
  //   more extensive 5-tuple lookups.
  struct flow_entry *getFlowEntry_Header(struct ip6_hdr* hdr) {
   if (hdr == NULL)
     //return &flow_table[T_DEF_PARENT_SLOT]; 
     return NULL;
   return getFlowEntry(ntohs(hdr->ip6_dst.s6_addr16[7]));
  }

  struct flow_entry *getFlowEntry_Match(struct flow_match *match) {
    dbg("IPRouting", "getFlowEntry_Match called for 0x%x\n", ntohs(match->dest));
    return getFlowEntry(ntohs(match->dest));
  }

  struct flow_entry *getNewEntry(struct flow_match *match) {
    uint8_t i;
    uint8_t place = N_FLOW_ENT;
    for (i = 0; i < N_FLOW_ENT; i++) {
      if (!IS_VALID_SLOT(&(flow_table[i]))) {
        flow_table[i].match.src = ntohs(match->src);
        flow_table[i].match.dest = ntohs(match->dest);

        dbg("IPRouting", "New flow entry slot provided in slot [%u]\n", i);
        return &(flow_table[i]);
      }
      if (flow_table[i].count == (N_FLOW_ENT - 1))
        place = i;
    }
 
    if (place == N_FLOW_ENT) {
      dbg("IPRouting", "The correct value of place doesn't exist!!\n");
      return NULL;
    }

    dbg("IPRouting", "Conflicted flow entry slot. Dest: 0x%x, slot 0x%x\n", flow_table[place].match.dest, place);
    for (i = 0; i < N_FLOW_CHOICES; i++) {
      if(IS_VALID_ENTRY(flow_table[place].entries[i])) {
        SET_INVALID_ENTRY(flow_table[place].entries[i]);
        if (IS_FULL_TYPE(flow_table[place].entries[i]))
          freeFullPath(flow_table[place].entries[i].pathE);
      }
    }
    SET_INVALID_SLOT(&(flow_table[place]));
    updateFlowCounts(&(flow_table[place]));
    ip_memclr((uint8_t *)(&(flow_table[place])), sizeof(struct flow_entry));
    return &(flow_table[place]);
  }
#endif

  struct neigh_entry *getNeighEntry(cmpr_ip6_addr_t a) {
    int i;
    for (i = 0; i < N_NEIGH; i++) {
      if (neigh_table[i].neighbor == a)
        return &(neigh_table[i]);
    }
    return NULL;
  }

#ifdef CENTRALIZED_ROUTING
  cmpr_ip6_addr_t nextHop_Flow(struct f_entry *fEntry) {
    if (IS_VALID_ENTRY(*fEntry)) {
      if (IS_HOP_TYPE(*fEntry)) return fEntry->nextHop;
      return fEntry->pathE->path[0];
    }
    return T_INVAL_NEIGH;
  }

  struct flow_path *getNewFlowPath() {
    uint8_t i;
    for (i = 0; i < N_FULL_PATH_ENTRIES; i++) {
      if (full_path_entries[i].path_len == 0)
        return &(full_path_entries[i]);
    }
    return NULL;
  }
  
  error_t freeFullPath(struct flow_path* path) {
    path->path_len = 0;
    return SUCCESS;
  }

  void reverseFlowMatch(struct rinstall_header *orig, 
                        struct flow_match *reverse,
                        struct ip6_hdr *iph) {

    printfUART("reverseFlowMatch: %i %i\n", ntohs(iph->ip6_dst.s6_addr16[7]),
               ntohs(iph->ip6_src.s6_addr16[7]));

    if (orig->match.src == htons(T_INVAL_NEIGH))
      reverse->src = htons(T_INVAL_NEIGH);
    else
      reverse->src = iph->ip6_src.s6_addr16[7];

    if (orig->match.dest == htons(T_INVAL_NEIGH)) // Shouldn't happen
      reverse->dest = htons(T_INVAL_NEIGH);
    else
      reverse->dest = iph->ip6_dst.s6_addr16[7];
  }  
  
  /*
   * Function takes the set of choices within a single flow_entry slot and arranges
   *  them in order of addition/modification.
   *
   * @entry_index - The index of the entry that is being uninstalled, or moved to
   *  the top of the stack. (Set this to N_FLOW_CHOICES to indicate that a new
   *  entry is being installed).
   * @install - Whether an entry is being installed or moved to the top of the stack
   *
   * TODO: Implement explicit flow entry removal
   */
  void sortFlowEntries(struct flow_entry *target, uint8_t entry_index, bool install) {
    struct f_entry f_temp;
    uint8_t i;
   
    dbg("IPRouting", "sortFlowEntries: Index: 0x%x, Install: 0x%x\n", entry_index, install);

    if (install && (entry_index < N_FLOW_CHOICES)) {
      ip_memcpy(&f_temp, &(target->entries[entry_index]), sizeof(struct f_entry));
    }