linkcache.cc

来自「在Linux下做的QuadTree的程序」· CC 代码 · 共 712 行

#include <god.h>
#include "path.h"
#include "routecache.h"
#include <list.h>
#ifdef DSR_CACHE_STATS
#include <cmu/dsr/cache_stats.h>
#endif

#define CURRENT_TIME Scheduler::instance().clock()

bool cache_ignore_hints = false;     // ignore all hints?
bool cache_use_overheard_routes = true; 

// Specifies whether or not to retain links after they go bad
static bool lc_cache_negative_links = false;

// When inserting/deleting link A->B, also insert/delete B->A.
static bool lc_bidirectional_links = true;

// Evict "unreachable" links from the cache.
static bool lc_evict_unreachable_links = false;

// The maximum number of nodes supported by the cache.
#define LC_MAX_NODES 50

static int verbose_debug = 0;

///////////////////////////////////////////////////////////////////////////

class Link {
public:
	Link(nsaddr_t dst) {
		ln_dst = dst;
		ln_flags = ln_cost = 0;
		ln_timeout = 0.0;
		ln_t = 0.0;
		ln_linktype = LT_NONE;
		ln_logstat = LS_UNLOGGED;
	}

	LIST_ENTRY(Link) ln_link;
	nsaddr_t   ln_dst;
	int        ln_flags;       // link status information
#define LINK_FLAG_UP 0x01

	/*
	 * Right now all links have the same cost (1). - josh
	 */
	int        ln_cost;        // cost of using the link

	/*
	 * the use of ln_timeout to expire links from the
	 * cache has not yet been implemented. - josh
	 */
	double     ln_timeout;     // when the link expires
#define LINK_TIMEOUT 0.0

	// mirror the values kept in class ID
	Time	   ln_t;
	Link_Type  ln_linktype;
	Log_Status ln_logstat;
};

LIST_HEAD(LinkHead, Link);

class LinkCache : public RouteCache {
friend class MobiHandler;

public:
	LinkCache();

	void noticeDeadLink(const ID&from, const ID& to, Time t);
	// the link from->to isn't working anymore, purge routes containing
	// it from the cache

	void noticeRouteUsed(const Path& route, Time t,
			     const ID& who_from);
	// tell the cache about a route we saw being used

	void addRoute(const Path& route, Time t, const ID& who_from);
	// add this route to the cache (presumably we did a route request
	// to find this route and don't want to lose it)

	bool findRoute(ID dest, Path& route, int for_me = 0);
	// if there is a cached path from us to dest returns true and fills in
	// the route accordingly. returns false otherwise
	// if for_use, then we assume that the node really wants to keep 
	// the returned route so it will be promoted to primary storage
	// if not there already
	int command(int argc, const char*const* argv);

protected:
	LinkHead lcache[LC_MAX_NODES + 1];
	// note the zeroth index is not used

	int addLink(const ID& from, const ID& to,
		    int flags, int cost = 1, double timeout = LINK_TIMEOUT);
	int delLink(const ID& from, const ID& to);
	Link* findLink(int from, int to);
	void purgeLink(void);
	void dumpLink(void);

	void Link_to_ID(Link* l, ID& id);

#ifdef DSR_CACHE_STATS
	void checkLink_logall(const ID& from, const ID& to, int action);
	void checkLink(const ID& from, const ID& to, int action);
	void periodic_checkCache();

	struct cache_stats stat;
#endif
private:
	////////////////////////////////////////////////////////////
	// Dijkstra's Algorithm

	int dirty;
	u_int32_t d[LC_MAX_NODES + 1];
	u_int32_t pi[LC_MAX_NODES + 1];
	bool S[LC_MAX_NODES + 1];
#define INFINITY 0x7fffffff

	void init_single_source(int s);
	void relax(u_int32_t u, u_int32_t v, u_int32_t w);
	int  extract_min_q(void);
	void dijkstra(void);
	void dump_dijkstra(int dst);
};

///////////////////////////////////////////////////////////////////////////

RouteCache *
makeRouteCache()
{
  return new LinkCache();
}

LinkCache::LinkCache() : RouteCache()
{
	int i = 0;

	for(i = 0; i <= LC_MAX_NODES; i++) {
		LIST_INIT(&lcache[i]);
	}
#ifdef DSR_CACHE_STATS
	stat.reset();
#endif
	dirty = 1;
}


int
LinkCache::command(int argc, const char*const* argv)
{
  if(argc == 2 && strcasecmp(argv[1], "startdsr") == 0)
    { 
      if (ID(1,::IP) == net_id) 
	trace("Sconfig %.5f using LINKCACHE", Scheduler::instance().clock());
      // FALL-THROUGH
    }

  if(argc == 3)
    {   
      if (strcasecmp(argv[1], "ip-addr") == 0)
        {
          assert(atoi(argv[2]) <= LC_MAX_NODES);
          // don't return
        } 
    }
  return RouteCache::command(argc, argv);
}


void
LinkCache::noticeDeadLink(const ID& from, const ID& to, Time)
{
	Link *l = findLink(from.addr, to.addr);

	if(lc_cache_negative_links == true) {
		if(l) {
			l->ln_flags &= ~LINK_FLAG_UP;
			l->ln_timeout = LINK_TIMEOUT;
		} else {
			addLink(from, to, 0);
		}
	}
	else {
		if(l) {
#ifdef DSR_CACHE_STATS
			checkLink(from, to, ACTION_DEAD_LINK);
#endif
			(void) delLink(from, to);
		}
	}
}

void
LinkCache::noticeRouteUsed(const Path& p, Time t, const ID& who_from)
{
  Path stub;
  int c;

  if(pre_noticeRouteUsed(p, stub, t, who_from) == 0)
	  return;
  
#ifdef DSR_CACHE_STATS
  int link_notice_count = stat.link_notice_count; 
  int link_notice_bad_count = stat.link_notice_bad_count;   
#endif

  /*
   * Add each link in the "path" to the route cache.
   */
  for(c = 0; c < stub.length() - 1; c++) {
	  if(addLink(stub[c], stub[c+1], LINK_FLAG_UP)) {
#ifdef DSR_CACHE_STATS
		checkLink(stub[c], stub[c+1], ACTION_NOTICE_ROUTE);
#endif
	  }
  }

#ifdef DSR_CACHE_STATS
  if(stat.link_notice_count > link_notice_count)
	  stat.route_notice_count++;
  if(stat.link_notice_bad_count > link_notice_bad_count)
	  stat.route_notice_bad_count++;
#endif
}

void
LinkCache::addRoute(const Path& route, Time t, const ID& who_from)
{
  Path rt;
  int c;

  if(pre_addRoute(route, rt, t, who_from) == 0)
	  return;
  
#ifdef DSR_CACHE_STATS
  int link_add_count = stat.link_add_count; 
  int link_add_bad_count = stat.link_add_bad_count;   
#endif

  for(c = 0; c < rt.length() - 1; c++) {
	  if(addLink(rt[c], rt[c+1], LINK_FLAG_UP)) {
#ifdef DSR_CACHE_STATS
		  checkLink(rt[c], rt[c+1], ACTION_ADD_ROUTE);
#endif
	  }
  }

#ifdef DSR_CACHE_STATS
  if(stat.link_add_count > link_add_count)
	  stat.route_add_count++;
  if(stat.link_add_bad_count > link_add_bad_count)
	  stat.route_add_bad_count++;
#endif
}

bool
LinkCache::findRoute(ID dest, Path& route, int for_me = 0)
{
	u_int32_t v;
	int rpath[MAX_SR_LEN];
	u_int32_t roff = 0;

	if(verbose_debug) dumpLink();

	/*
	 * Compute all of the shortest paths...
	 */
	if(dirty) {
		dijkstra();

		// remove all of the links for nodes that are unreachable
		if(lc_evict_unreachable_links == true) {
			purgeLink();
		}
	}
	if(verbose_debug) dump_dijkstra(dest.addr);

	/*
	 * Trace backwards to figure out the path to DEST
	 */
	for(v = dest.addr; d[v] < INFINITY; v = pi[v]) {
		assert(v >= 1 && v <= LC_MAX_NODES);
		if (roff >= MAX_SR_LEN) {
 		        // path between us and dest is too long to be useful
		        break;
		}

		rpath[roff] = v;
		roff++;

		if(v == net_id.addr)
			break;
	}

	if(roff < 2 || d[v] == INFINITY || roff >= MAX_SR_LEN) {
#ifdef DSR_CACHE_STATS
		stat.route_find_count += 1;
		if (for_me) stat.route_find_for_me += 1; 
		stat.route_find_miss_count += 1;
#endif
		return false; // no path
	}

	/*
	 * Build the path that we need...
	 */
	ID id;

	route.reset();

	id.addr = net_id.addr;  // source route is rooted at "us"
	id.type = ::IP;
	id.link_type = LT_NONE;
	id.log_stat = LS_NONE;
	route.appendToPath(id);

	for(v = 1; v < roff ; v++) {
		assert((int) (roff - v - 1) >= 0 && (roff - v - 1) < MAX_SR_LEN);

		Link *l = findLink(route[v-1].addr, rpath[roff - v - 1]);
		assert(l);

		id.addr = rpath[roff - v - 1];
		id.type = ::IP;
		id.link_type = LT_NONE;
		id.log_stat = LS_NONE;
		route.appendToPath(id);

		route[v-1].t = l->ln_t;
		route[v-1].link_type = l->ln_linktype;
		route[v-1].log_stat = l->ln_logstat;
	}
	
#ifdef DSR_CACHE_STATS
	int bad = checkRoute_logall(&route, ACTION_FIND_ROUTE, 0);
	stat.route_find_count += 1; 
	if (for_me) stat.route_find_for_me += 1;     
	stat.route_find_bad_count += bad ? 1 : 0;
	stat.link_find_count += route.length() - 1;
	stat.link_find_bad_count +=  bad;
#endif
	return true;
}


void
LinkCache::Link_to_ID(Link *l, ID& id)
{
	id.addr = l->ln_dst;
	id.type = ::IP;
	id.t = l->ln_t;
	id.link_type = l->ln_linktype;
	id.log_stat = l->ln_logstat;
}

///////////////////////////////////////////////////////////////////////////

/*
 * Dijkstra's algorithm taken from CLR.
 */

void
LinkCache::init_single_source(int s)
{
	int v;

	for(v = 1; v <= LC_MAX_NODES; v++) {
		d[v] = INFINITY;
		pi[v] = 0; // invalid node ID

		S[v] = false;
	}
	d[s] = 0;
}

void
LinkCache::relax(u_int32_t u, u_int32_t v, u_int32_t w)
{
	assert(d[u] < INFINITY);

	if(d[v] > d[u] + w) {
		d[v] = d[u] + w;
		pi[v] = u;
	}
}


int
LinkCache::extract_min_q()
{
	int u;
	int min_u = 0;

	for(u = 1; u <= LC_MAX_NODES; u++) {
		if(S[u] == false && d[u] < INFINITY && (min_u == 0 || d[u] < d[min_u])) {
			min_u = u;
		}
	}
	return min_u; // (min_u == 0) ==> no valid link
}

void
LinkCache::dijkstra()
{
	int u;	
	Link *v;

	init_single_source(net_id.addr);

	while((u = extract_min_q()) != 0) {
		S[u] = true;
		v = lcache[u].lh_first;
		for( ; v; v = v->ln_link.le_next) {
			if(v->ln_flags & LINK_FLAG_UP) {
				relax(u, v->ln_dst, v->ln_cost);
			}
		}
	}
	dirty = 0;  // all of the info is up-to-date
}

void
LinkCache::dump_dijkstra(int dst)
{
	static char tbuf[512];
	u_int32_t u, toff = 0;

	bzero(tbuf, sizeof(tbuf));
	sprintf(tbuf, "SRC %.9f _%s_ dijkstra *%d* ",
		CURRENT_TIME, net_id.dump(), dst);
	toff = strlen(tbuf);

	for(u = 1; u <= LC_MAX_NODES; u++) {
		if(d[u] < INFINITY) {
			sprintf(tbuf+toff, "%d,%d,%d ", u, d[u], pi[u]);
			toff = strlen(tbuf);
			assert(toff < sizeof(tbuf));
		}
	}

	trace("%s", tbuf);
}
	

///////////////////////////////////////////////////////////////////////////

int
LinkCache::addLink(const ID& from, const ID& to,
		   int flags, int cost, double timeout)
{
	Link *l;
	int rc = 0;

	if((l = findLink(from.addr, to.addr)) == 0) {
		l = new Link(to.addr);
		assert(l);
		LIST_INSERT_HEAD(&lcache[from.addr], l, ln_link);
		dirty = 1;
		rc = 1;
	}
	l->ln_t = CURRENT_TIME;
	l->ln_linktype = from.link_type;
	l->ln_flags |= flags;
	l->ln_cost = cost;
	l->ln_timeout = timeout;

	if(lc_bidirectional_links == false)
		return rc;

	/*
	 * Add the "other" direction of the link...
	 */
	if((l = findLink(to.addr, from.addr)) == 0) {
		l = new Link(from.addr);
		assert(l);
		LIST_INSERT_HEAD(&lcache[to.addr], l, ln_link);
		dirty = 1;
	}
	l->ln_t = CURRENT_TIME;
	l->ln_linktype = from.link_type;
	l->ln_flags |= flags;
	l->ln_cost = cost;
	l->ln_timeout = timeout;

	return rc;
}

int
LinkCache::delLink(const ID& from, const ID& to)
{
	Link *l;
	int rc = 0;

	if((l = findLink(from.addr, to.addr))) {
		LIST_REMOVE(l, ln_link);
		delete l;
		dirty = 1;
		rc = 1;
	}

	if(lc_bidirectional_links == false)
		return rc;

	/*
	 * Remove the "other" direction of the link...
	 */
	if((l = findLink(to.addr, from.addr))) {
		LIST_REMOVE(l, ln_link);
		delete l;
		dirty = 1;
	}

	return rc;
}

Link*
LinkCache::findLink(int from, int to)
{
	Link *l;

	for(l = lcache[from].lh_first; l; l = l->ln_link.le_next) {
		if(l->ln_dst == to) {
			return l;
		}
	}
	return 0;
}

void
LinkCache::purgeLink()
{
	int u;
	Link *l;

	for(u = 1; u <= LC_MAX_NODES; u++) {
		if(d[u] == INFINITY) {
			ID from, to;

			from.addr = u;
			from.type = ::IP;
			from.link_type = LT_NONE;
			from.log_stat = LS_NONE;

			l = lcache[u].lh_first;
			for( ; l; l = l->ln_link.le_next) {
				Link_to_ID(l, to);
				checkLink_logall(from, to, ACTION_EVICT);
				(void) delLink(from, to);
			}
		}
	}
}


void
LinkCache::dumpLink()
{
	Link *l;
	int i;
	static char tbuf[512];
	u_int32_t toff = 0;

	bzero(tbuf, sizeof(tbuf));
	sprintf(tbuf, "SRC %.9f _%s_ dump-link ", CURRENT_TIME, net_id.dump());
	toff = strlen(tbuf);

	for(i = 1; i <= LC_MAX_NODES; i++) {
		for(l = lcache[i].lh_first; l; l = l->ln_link.le_next) {
			sprintf(tbuf+toff, "%d->%d, ", i, l->ln_dst);
			toff = strlen(tbuf);
			assert(toff < sizeof(tbuf));
		}
	}

	trace("%s", tbuf);
}

#ifdef DSR_CACHE_STATS

/*
 * Called only from "purgeLink"
 */
void
LinkCache::checkLink_logall(const ID& from, const ID& to, int action)
{
	Link *l = findLink(from.addr, to.addr);

	assert(action == ACTION_EVICT);
	assert(l);

	if(God::instance()->hops(from.addr, to.addr) != 1) {
		trace("SRC %.9f _%s_ %s [%d %d] %s->%s dead %d %.9f",
		      CURRENT_TIME, net_id.dump(),
		      action_name[action], 0, 0,
		      from.dump(), to.dump(),
		      l->ln_linktype, l->ln_t);
	}
}

void
LinkCache::checkLink(const ID& from, const ID& to, int action)
{
	Link *l = findLink(from.addr, to.addr);
	int alive = 0;

	assert(l);

	if(God::instance()->hops(from.addr, to.addr) != 1) {
		if(l->ln_logstat == LS_UNLOGGED) {
			trace("SRC %.9f _%s_ %s [%d %d] %s->%s dead %d %.9f",
				CURRENT_TIME, net_id.dump(),
				action_name[action], 0, 0,
				from.dump(), to.dump(),
				l->ln_linktype, l->ln_t);
			l->ln_logstat = LS_LOGGED;
		}
	} else {
		alive = 1;
		if(l->ln_logstat == LS_LOGGED) {
			trace("SRC %.9f _%s_ resurrected-link [%d %d] %s->%s dead %d %.9f",
				CURRENT_TIME, net_id.dump(), 0, 0,
				from.dump(), to.dump(),
				l->ln_linktype, l->ln_t);
			l->ln_logstat = LS_UNLOGGED;
		}
        }

	switch(action) {
	case ACTION_ADD_ROUTE:
		stat.link_add_count += 1;
		if(alive == 0){
		        stat.link_add_bad_count += 1;
		}
		if(l->ln_linktype == LT_TESTED)
			stat.link_add_tested += 1;
		break;

	case ACTION_NOTICE_ROUTE:
		stat.link_notice_count += 1;
		if(alive == 0){
			stat.link_notice_bad_count += 1;
		}
		if(l->ln_linktype == LT_TESTED)
			stat.link_notice_tested += 1;
		break;
	}
}

void
LinkCache::periodic_checkCache()
{
  int c;
  int link_count = 0;
  int link_bad_count = 0;
  double link_bad_time = 0.0;
  int link_bad_tested = 0;
  int link_good_tested = 0;

  for(c = 1; c <= LC_MAX_NODES; c++) {
	Link *v = lcache[c].lh_first;
	for( ; v; v = v->ln_link.le_next) {
		link_count += 1;
		if(God::instance()->hops(c, v->ln_dst) != 1) {
			link_bad_count += 1;
			link_bad_time += CURRENT_TIME - v->ln_t;
			if(v->ln_linktype == LT_TESTED)
				link_bad_tested += 1;
		} else {
			if(v->ln_linktype == LT_TESTED)
				link_good_tested += 1;
		}
	}
  }

  trace("SRC %.9f _%s_ cache-summary %d %d %d %d | %d %.9f %d %d | %d %d %d %d %d | %d %d %d %d %d | %d %d %d %d %d %d",
	CURRENT_TIME, net_id.dump(),
        0, //route_count,
        0, // route_bad_count,
        link_count, // subroute_count,
        0, // subroute_bad_count,

        link_bad_count,
        link_bad_count ? link_bad_time/link_bad_count : 0.0,
        link_bad_tested,
        link_good_tested,

        stat.route_add_count,     // always 0 -- not increment
        stat.route_add_bad_count, // always 0 -- not increment
        stat.link_add_count, // stat.subroute_add_count,
        stat.link_add_bad_count, // stat.subroute_add_bad_count,
        stat.link_add_tested,
             
        stat.route_notice_count,
        stat.route_notice_bad_count,
        stat.link_notice_count, // stat.subroute_notice_count,
        stat.link_notice_bad_count, // stat.subroute_notice_bad_count,
        stat.link_notice_tested,
             
        stat.route_find_count,
	stat.route_find_for_me,
        stat.route_find_bad_count,
        stat.route_find_miss_count,
        stat.subroute_find_count,
        stat.subroute_find_bad_count);
  stat.reset();
}

#endif