iproutingp.nc

tinyos-2.x.rar

    for (i = ((entry_index < N_FLOW_CHOICES)? (entry_index):(N_FLOW_CHOICES - 1)); i > 0; i--) {
      ip_memcpy(&(target->entries[i]), &(target->entries[i-1]), sizeof(struct f_entry));
    }

    if (install && (entry_index < N_FLOW_CHOICES))
      ip_memcpy(&(target->entries[0]), &f_temp, sizeof(struct f_entry));
    else
      ip_memclr((uint8_t *)(&(target->entries[0])), sizeof(struct f_entry));
  }

  void updateFlowCounts(struct flow_entry *target) {
    uint8_t i;
    if (target == NULL) return;
    dbg("IPRouting", "updateFlowCounts\n");
    
    // Just used or installed something
    if (IS_VALID_SLOT(target)) {
      for(i = 0; i < N_FLOW_ENT; i++) {
        if (!(IS_VALID_SLOT(&(flow_table[i])))) continue;
        if (flow_table[i].count < target->count) flow_table[i].count++;
      }
      target->count = 0;
    } else {
      for (i = 0; i < N_FLOW_ENT; i++) {
        if (!(IS_VALID_SLOT(&(flow_table[i])))) continue;
        if (flow_table[i].count > target->count) flow_table[i].count--;
      }
      target->count = N_FLOW_ENT;
    }
  }

  // Helper Functions
  error_t installEntry(struct ip6_hdr *iph, struct rinstall_header *rih, struct ip6_route *route) {
    struct flow_entry *entry;
    struct flow_match reverse_match;
    uint16_t current, path_len, 
      reverse = 0,
      fullPath = (rih->flags & HYDRO_INSTALL_METHOD_MASK) == HYDRO_METHOD_SOURCE;
    cmpr_ip6_addr_t *path;
    uint8_t i;

    // if this is a METHOD_SOURCE install, and the path is carried in
    // the routing header we must be on the far end of the install,
    // and so need to reverse everything.


    if (fullPath && rih->path_len == 0) reverse = 1;
    if (!fullPath) {
      printfUART("not fp, route: %p  rip: %i\n", route, rih->path_len);
      reverse = rih->flags & HYDRO_INSTALL_REVERSE;
      if (!reverse && route && route->segs_remain == 0 && rih->path_len == 0) return SUCCESS;
      if (reverse && rih->path_len > 0) return SUCCESS;
    }

    printfUART("install rev: %i fp: %i\n", reverse, fullPath)

    if (rih->path_len == 0) {
      if (route == NULL) return FAIL;
      current = ROUTE_NENTRIES(route) - route->segs_remain;
      path = route->hops;
      path_len = ROUTE_NENTRIES(route);
    } else {
      current = reverse ? rih->path_len - 1 : 0;
      path = rih->path;
      path_len = rih->path_len;
    }
    
    dbg("Install", "installEntry: flags: 0x%x\n", rih->flags);
    
    if (!reverse && 
        ((entry = getFlowEntry_Match(&(rih->match))) == NULL) && 
        ((entry = getNewEntry(&(rih->match))) == NULL)) {
      dbg("Install", "installEntry: forward path has no match and no room in flow table\n");
      return FAIL;
    } else if (reverse) {
      reverseFlowMatch(rih, &reverse_match, iph);
      if (((entry = getFlowEntry_Match(&(reverse_match))) == NULL) && 
          ((entry = getNewEntry(&(reverse_match))) == NULL)) {
        dbg("Install", "installEntry: reverse path has no match and no room in flow table\n");
        return FAIL;
       }
    }

    //Inefficient duplicate detection
    for (i = 0; i < N_FLOW_CHOICES; i++) {
      printfUART("checking dup %i %i\n", nextHop_Flow(&entry->entries[i]),
                 ntohs(path[reverse ? (current - 1) : current]));
      if (IS_VALID_ENTRY(entry->entries[i]) && 
          (nextHop_Flow(&entry->entries[i]) == 
           ntohs(path[reverse ? (current - 1) : current])) && 
          !fullPath) { 
        dbg("Install", "This choice already exists in flow table!\n");
        // Since order indicates order of arrival, need to move this one up higher
        if (i != 0) {
          sortFlowEntries(entry, i, TRUE);
        }
        return SUCCESS;
      }
      if (IS_VALID_ENTRY(entry->entries[i]) && IS_FULL_TYPE(entry->entries[i])) {
        dbg("Install", "Removing exiting source choice\n");
        entry->entries[0].pathE->path_len = 0;
        SET_INVALID_ENTRY(entry->entries[0]);        
      }
    }
    

    if (IS_VALID_ENTRY(entry->entries[0]))
      sortFlowEntries(entry, N_FLOW_CHOICES, TRUE);
    if (fullPath) {
      if ((entry->entries[0].pathE = getNewFlowPath()) == NULL) {
        dbg("Install", "No room available for new full path entry\n");
        return FAIL;
      }
      for (i = 0; i < path_len; i++) {
        entry->entries[0].pathE->path[i] = ntohs(path[(reverse ? (path_len - i - 1): i)]);
        dbg("Install", "Put node 0x%x as hop [%u]\n", entry->entries[0].pathE->path[i], (i));
      }
      entry->entries[0].pathE->path_len = path_len;
    } else {
      entry->entries[0].nextHop = ntohs(path[(reverse? (current - 1) : current)]);
      dbg("Install", "Put node 0x%x as next hop\n", entry->entries[0].nextHop);
    }
    SET_VALID_ENTRY((entry->entries[0]));
    SET_VALID_SLOT(entry);
    (fullPath? (SET_FULL_TYPE(entry->entries[0])) : (SET_HOP_TYPE(entry->entries[0])));
   
    updateFlowCounts(entry); 
    printTable();
    return SUCCESS;
  }

  error_t uninstallEntry(struct rinstall_header *rih) {
    struct flow_entry *entry;
    //struct neigh_entry *neigh;
    uint8_t i;

    // don't support reverse install
    if (rih->flags & HYDRO_INSTALL_REVERSE) return FAIL;
    // only work for source installs
    if ((rih->flags & HYDRO_INSTALL_METHOD_MASK) != HYDRO_METHOD_SOURCE) return FAIL;
    if ((entry = getFlowEntry_Match(&(rih->match))) == NULL)
      return FAIL;
    
    for (i = 0; i < N_FLOW_CHOICES; i++) {
      if (IS_VALID_ENTRY(entry->entries[i])) {
        SET_INVALID_ENTRY(entry->entries[i]);
        SET_INVALID_SLOT(entry);
        freeFullPath(entry->entries[i].pathE);
      }
    }
    return SUCCESS;
  }
#endif


  event void IPExtensions.handleExtensions(uint8_t label,
                                           struct ip6_hdr *iph,
                                           struct ip6_ext *hop,
                                           struct ip6_ext *dst,
                                           struct ip6_route *route,
                                           uint8_t nxt_hdr) {
#ifdef CENTRALIZED_ROUTING
    struct tlv_hdr *tlv = NULL;
    struct rinstall_header *rih;
    uint8_t method;
    bool forMe = call IPRouting.isForMe(iph), isHop = FALSE;

    printfUART("handling extension header!\n");

    if (dst != NULL) tlv = call IPExtensions.findTlv(dst, TLV_TYPE_INSTALL);
    if (tlv == NULL && hop != NULL) { tlv = call IPExtensions.findTlv(hop, TLV_TYPE_INSTALL); isHop = TRUE; }
    if (tlv == NULL) return;
    rih = (struct rinstall_header *)(tlv + 1);
    // first, install the entry if it's for me
    method = (rih->flags & HYDRO_INSTALL_METHOD_MASK);


    if (!forMe) {
      if (method == HYDRO_METHOD_HOP    && !isHop) return;
      if (method == HYDRO_METHOD_SOURCE) return;
    }
    if (!(rih->flags & HYDRO_INSTALL_UNINSTALL_MASK)) {
      installEntry(iph, rih, route);
    } else {
      // uninstall only returns
      uninstallEntry(rih);
      return;
    }

    if (method == HYDRO_METHOD_HOP && (rih->flags & HYDRO_INSTALL_REVERSE)) {
      // a little clunky, perhaps, but this is sort of how
      // installEntry expects things to work.
      rih->flags &= ~HYDRO_INSTALL_REVERSE;
      installEntry(iph, rih, route);
      rih->flags |= HYDRO_INSTALL_REVERSE;
    }

    if ( (forMe && rih->path_len > 0 && rih->path_len < 10) && 

         // if it's a source install, we don't need to generate a new
         // message unless the command is for us to also install the reverse path.
         ((method == HYDRO_METHOD_SOURCE &&
           rih->flags & HYDRO_INSTALL_REVERSE) ||
          // if it's a hop-by-hop install, we always need to generate a
          // new message to do the install.  however, only want this to
          // happen once, and since along the path the route install will be
          // carried as a hop-by-hop options, this check is sufficient.
          (method == HYDRO_METHOD_HOP && !isHop))) {
      
      // in either case the actual route to install must be in the
      // route install header
      uint16_t plen = sizeof(struct ip6_route) + (sizeof(cmpr_ip6_addr_t) * rih->path_len) +
        sizeof(struct ip6_ext) + sizeof(struct tlv_hdr) + 
        sizeof(struct rinstall_header);
      struct uint8_t *buf = ip_malloc(sizeof(struct split_ip_msg) + plen);
      struct split_ip_msg *ipmsg;
      struct ip6_ext   *newext;
      struct tlv_hdr   *newtlv;
      struct rinstall_header *newrih;
      struct ip6_route *iproute;
      printfUART("installing reverse path to 0x%x\n", rih->match.dest);

      if (buf == NULL) return;
      ip_memclr((void *)buf, sizeof(struct split_ip_msg) + plen);

      ipmsg = (struct split_ip_msg *)buf;
      newext = (struct ip6_ext *)(ipmsg + 1);
      newtlv = (struct tlv_hdr *)(newext + 1);
      newrih = (struct rinstall_header *)(newtlv + 1);
      iproute = (struct ip6_route *)(newrih + 1);
      
      ipmsg->hdr.nxt_hdr = (method == HYDRO_METHOD_SOURCE) ? IPV6_DEST : IPV6_HOP;
      ipmsg->hdr.plen = htons(plen);
      ipmsg->data = (uint8_t *)(ipmsg  + 1);
      ipmsg->data_len = plen;
      ipmsg->headers = NULL;
      call IPAddress.getIPAddr(&ipmsg->hdr.ip6_src);
      call IPAddress.getIPAddr(&ipmsg->hdr.ip6_dst);
      ipmsg->hdr.ip6_src.s6_addr16[7] = rih->match.dest;

      newext->nxt_hdr = IPV6_ROUTING;
      newext->len = sizeof(struct ip6_ext) + sizeof(struct tlv_hdr) + 
        sizeof(struct rinstall_header);
      newtlv->type = TLV_TYPE_INSTALL;
      newtlv->len = sizeof(struct tlv_hdr) + sizeof(struct rinstall_header);

      ip_memcpy(&newrih->match, &rih->match, sizeof(struct flow_match));
      newrih->flags = rih->flags;
      newrih->path_len = 0;

      iproute->nxt_hdr = IPV6_NONEXT;
      iproute->len = sizeof(struct ip6_route) + (sizeof(cmpr_ip6_addr_t) * rih->path_len);
      iproute->type = IP6ROUTE_TYPE_SOURCE;
      iproute->segs_remain = rih->path_len;
      ip_memcpy(iproute->hops, rih->path, sizeof(cmpr_ip6_addr_t) * rih->path_len);
      
      call TGenSend.bareSend(ipmsg, iproute, IP_NOHEADERS);
      ip_free(buf);
      // we should be all set up now.  
    }
#endif
  }

  
  uint16_t getConfidence(struct neigh_entry *neigh) {
    //uint8_t i;
    uint16_t conf = 0;
    if (neigh != NULL && IS_NEIGH_VALID(neigh)) {
      //for (i = 0; i < N_EPOCHS_COUNTED; i++) {
      //conf += neigh->stats[(current_epoch + N_EPOCHS - i) % N_EPOCHS].total;
        //}
      conf = neigh->stats[LONG_EPOCH].total;
    }
    return conf;
  }

  uint16_t getReceptions(struct neigh_entry *neigh) {
    //uint8_t i;
    uint16_t receptions = 0;
    if ((neigh != NULL) && (IS_NEIGH_VALID(neigh))) {
      //for (i = 0; i < N_EPOCHS_COUNTED; i++) {
      //receptions += neigh->stats[(current_epoch + N_EPOCHS - i) % N_EPOCHS].receptions;
        //}
      receptions += neigh->stats[receptions].receptions;
    }
    return receptions;
  }

  uint16_t getSuccess(struct neigh_entry *neigh) {
    //uint8_t i;
    uint16_t succ = 0;
    if ((neigh != NULL) && (IS_NEIGH_VALID(neigh))) {
      //for (i = 0; i < N_EPOCHS_COUNTED; i++) {
      //succ += neigh->stats[(current_epoch + N_EPOCHS - i) % N_EPOCHS].success;
      //}
      succ += neigh->stats[LONG_EPOCH].success;
    }
    return succ;
  }

  uint16_t getLinkCost(struct neigh_entry *neigh) {
    uint16_t conf, succ;
    conf = getConfidence(neigh);
    succ = getSuccess(neigh);
    // we can return a real confidence if we have enough data
    if (succ == 0 || conf == 0) return 0xff;
    return ((conf * 10) / succ);
  }
        

  void printTable() {
#ifdef PRINTFUART_ENABLED
    uint8_t i;
#ifdef CENTRALIZED_ROUTING
    uint8_t j, k;
#endif
    dbg("Table", "----------------------------------------___\n");
    dbg("Table", "ind\tvalid\tmature\tneigh\thops\tconf\trecep\tcost\tetx\tlqi\tmetric\n");
    for (i = 0; i < N_NEIGH; i++) {
      if (&neigh_table[i] == default_route)
        dbg("Table", "-- default --\n");
      dbg("Table", "0x%x\t0x%x\t0x%x\t0x%x\t0x%x\t0x%x\t0x%x\t0x%x\t0x%x\t0x%x\t0x%x\n", i, 
          (neigh_table[i].flags & T_VALID_MASK), (IS_MATURE(&(neigh_table[i]))),
          neigh_table[i].neighbor, neigh_table[i].hops, getConfidence(&(neigh_table[i])), 
          getReceptions(&(neigh_table[i])), neigh_table[i].costEstimate, 
          getLinkCost(&(neigh_table[i])), neigh_table[i].linkEstimate, 
          getMetric(&(neigh_table[i])));
    }
#ifdef CENTRALIZED_ROUTING
    dbg("Table", "------ Valid Flow Tables -------\n");
    dbg("Table", "valid\ttype\tnext\n");
    for (j = 0; j < N_FLOW_ENT; j++) {
      if (!(IS_VALID_SLOT(&(flow_table[j])))) continue;
      dbg("Table", "\n -- Flow Table Slot [%u] , Dest: [0x%x] , Count: [0x%x] --\n", 
          j, flow_table[j].match.dest, flow_table[j].count);
      for (i = 0; i < N_FLOW_CHOICES; i++) {
        if (IS_VALID_ENTRY(flow_table[j].entries[i]) && 
            IS_FULL_TYPE(flow_table[j].entries[i])) {
          dbg("Table", "0x%x\t0x%x\t", 
              IS_VALID_ENTRY(flow_table[j].entries[i]), 
              IS_FULL_TYPE(flow_table[j].entries[i]));
          for (k = 0; k < flow_table[j].entries[i].pathE->path_len; k++)
            dbg("Table", "0x%x\t", 
                flow_table[j].entries[i].pathE->path[k]);
          dbg("Table", "\n");
        } else {
          dbg("Table", "0x%x\t0x%x\t0x%x\n", 
              IS_VALID_ENTRY(flow_table[j].entries[i]), 
              IS_FULL_TYPE(flow_table[j].entries[i]),
              nextHop_Flow(&(flow_table[j].entries[i])));
        }
      }
    }
#endif
    dbg("Table", "----------------------------------------\n");