nwstate.c

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 <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <float.h>
#include <time.h>
#include <sys/time.h>
#include "lib6lowpan/lib6lowpan.h"

#include "nwstate.h"
#include "hashtable.h"
#include "logging.h"
#include "routing.h"
#include "vty/vty.h"

struct hashtable *links;
struct hashtable *routers;

router_t *router_list = NULL;
int routes_out_of_date = 1;

extern struct in6_addr __my_address;


void compute_routes(node_id_t v1);
//
// general boilerplate
// 

static unsigned int hash_link(void *k) {
  link_key_t *l = (link_key_t *)k;
  if (l->r1 > l->r2)
    return (l->r1 | (l->r2 << 16));
  else
    return (l->r2 | (l->r1 << 16));
}
static int link_equal(void *k1, void *k2) {
  link_key_t *l1 = (link_key_t *)k1;
  link_key_t *l2 = (link_key_t *)k2;
  return ((l1->r1 == l2->r1 && l1->r2 == l2->r2) ||
          (l1->r1 == l2->r2 && l1->r2 == l2->r1));
}

static unsigned int hash_router(void *k) {
  return *((router_key_t *)k);
}

static int router_equal(void *k1, void *k2) {
  return ((router_t *)k1)->id == ((router_t *)k2)->id;
}

int do_print = 0;
int do_routes = 0;
int printCount = 0;

int nw_print_dotfile(char *filename) {
  router_t *r;
  link_t *e;
  FILE *fp = fopen (filename, "w");
  if (fp == NULL) return -1;
  info("writing topology to '%s'\n", filename);
  printCount ++;
  fprintf(fp, "digraph Network {\n");
  
  for (r = router_list; r != NULL; r = r->next) {
    for (e = r->links; e != NULL; e = e->next1) {
      if (e->pc < printCount) {
        fprintf(fp, "  \"0x%x\" -> \"0x%x\" [label=\"%f\"]\n", e->n1->id, e->n2->id, e->qual);
        e->pc = printCount;
      }
    }
    for (e = r->links; e != NULL; e = e->next2) {
      if (e->pc < printCount) {
        fprintf(fp, "  \"0x%x\" -> \"0x%x\" [label=\"%f\"]\n", e->n1->id, e->n2->id, e->qual);
        e->pc = printCount;
      }
    }
  }

  fprintf(fp, "}\n");
  fclose(fp);
  return 0;
}


void nw_print_routes(int fd, int argc, char **argv) {
  VTY_HEAD;
  router_t *r,*s;
  for (r = router_list; r != NULL; r = r->next) {
    VTY_printf("  0x%x: ", r->id);
    for (s = r->sp.prev; s != NULL; s = s->sp.prev) {
      VTY_printf("0x%x", s->id);
      if (r->isController) VTY_printf("[C] ");
      else VTY_printf(" ");
    }
    VTY_printf("\r\n");
    VTY_flush();
  }
}

void nw_test_routes(int fd, int argc, char **argv) {
  node_id_t dest = ntohs(__my_address.s6_addr16[7]);
  debug("nwstate: computing new routes (root: 0x%x)\n", ntohs(__my_address.s6_addr16[7]));
  compute_routes(dest);
}

void nw_print_links(int fd, int argc, char **argv) {
  VTY_HEAD;
  struct tm *ltime;
  int target = -1;
  router_t *r;
  link_t *l;

  if (argc == 2) {
    if (sscanf(argv[1], "%i", &target) == 0) {
      VTY_printf("invalid node\r\n");
      VTY_flush();
      return;
    }
  }

  for (r = router_list; r != NULL; r = r->next) {
    char flags[16]; int pos = 0;
    if (target >= 0 && r->id != target) continue;

    flags[0] = '\0';
    if (r->isProxying || r->isController) {
      flags[pos++] = '['; 
      if (r->isController) flags[pos++] = 'C';
      if (r->isProxying) flags[pos++] = 'P';
      flags[pos++] = ']';
      flags[pos++] = '\0';
    }

    VTY_printf(" 0x%x%s: dist: ", r->id, flags);
    if (r->sp.dist == FLT_MAX)
      VTY_printf("Inf");
    else
      VTY_printf("%.1f", r->sp.dist);
    if (!r->isController) {
      ltime = localtime(&r->lastReport.tv_sec);
      VTY_printf(" reported: " ISO8601_FMT(ltime, &r->lastReport));
    }

    VTY_printf("\r\n");
    for (l = r->links; l != NULL; l = (r == l->n1) ? l->next1 : l->next2) {
      if (r == l->n1) {
        VTY_printf("  --> 0x%x [%.1f]\r\n", l->n2->id, l->qual);
      }
    }
    VTY_printf("\r\n");
    VTY_flush();
  }
}

void nw_add_sticky_edge(int fd, int argc, char **argv) {
  VTY_HEAD;
  int v1, v2;
  if (argc == 3) {
    link_t *l;
    struct topology_entry te;
    v1 = atoi(argv[1]);
    v2 = atoi(argv[2]);
    VTY_printf("adding sticky edge between %i and %i\r\n", v1, v2);
    te.etx = 10;
    te.conf = 255;
    te.hwaddr = htons(v2);
    l = nw_add_incr_edge(v1, &te);
    l->marked = L_STICKY;
  } else {
    VTY_printf("add a link: '%s <n1> <n2>'\r\n", argv[0]);
  }
  VTY_flush();
}

void nw_inval_node_sh(int fd, int argc, char **argv) {
  VTY_HEAD;
  int int_arg;
  if (argc == 2) {
    int_arg = atoi(argv[1]);
    VTY_printf("invalidating node 0x%x\n", int_arg);
    nw_inval_node(int_arg);
  }
  VTY_flush();
}
//
// helpers
// 

router_t *nw_get_router(node_id_t rid) {
  return hashtable_search(routers, &rid);
}

router_t *get_insert_router(node_id_t rid) {
  router_key_t *key;
  router_t *ret = nw_get_router(rid);
  if (ret == NULL) {
    key = (router_key_t *)malloc(sizeof(router_key_t));
    ret = (router_t *)malloc(sizeof(router_t));
    memset(ret, 0, sizeof(router_t));

    ret->id = rid;
    ret->links = NULL;
    ret->next = router_list;

    ret->reports = 0;
    ret->lastSeqno = -1;

    ret->isProxying = FALSE;
    ret->isController = FALSE;

    ret->sp.dist = FLT_MAX;
    ret->sp.prev = NULL;

    router_list = ret;

    *key = rid;
    hashtable_insert(routers, key, ret);
  }
  return ret;
}


//
// network state API impl.
//

int nw_init() {
  router_t *r;
  links   = create_hashtable(16, hash_link,   link_equal);
  routers = create_hashtable(16, hash_router, router_equal);
  r = get_insert_router(ntohs(__my_address.s6_addr16[7]));
  r->isController = TRUE;
  return 0;
}

/*
 * Adds an observation of the link (v1, v2) to the database.  This
 * implicitly adds the reverse edge for now, as well.
 */
link_t *nw_add_incr_edge(node_id_t v1, struct topology_entry *te) {
  link_key_t key;
  link_t *link_str;
  node_id_t v2 = ntoh16(te->hwaddr);
  key.r1 = v1;
  key.r2 = v2;

  link_str = hashtable_search(links, &key);
  if (link_str == NULL) {
    link_key_t *new_key = (link_key_t *)malloc(sizeof(link_key_t));
    router_t *r1 = get_insert_router(v1);
    router_t *r2 = get_insert_router(v2);
    link_str = (link_t *)malloc(sizeof(link_t));
    memset(link_str, 0, sizeof(link_t));

    new_key->r1 = v1;
    new_key->r2 = v2;

    // point the links at their routers
    link_str->n1 = r1;
    link_str->n2 = r2;
    // add this link to the head of the linked list of edges each router maintains
    link_str->next1 = r1->links;
    link_str->next2 = r2->links;

    link_str->n1_reportcount = 0;
    link_str->n2_reportcount = 0;
    
    r1->links = link_str;
    r2->links = link_str;

    link_str->pc = 0;

    
    hashtable_insert(links, new_key, link_str);

  } 

  link_str->marked = L_REPORTED;
  link_str->qual = ((float)(te->etx)) / 10.0;
  link_str->conf = te->conf;
  debug("nw_add_incr_edge [%i -> %i]: qual: %f conf: %i\n", 
        v1, v2, link_str->qual, link_str->conf);
  (v1 == link_str->n1->id) ? link_str->n1_reportcount++ :
    link_str->n2_reportcount++;

  return link_str;
}

/*
 * Returns a route from v1 to v2 as a linked list.
 *
 * quadratic-time dijkstra implementation: no priority queue
 */
/*