chord.c

P2P模拟器

LocTable::succ(ConsistentHash::CHID id, int status)
{
  vector<Chord::IDMap> v = succs(id, 1, status);
  uint vsz = v.size();
  if (vsz > 0) {
    return v[0];
  }
  Chord::IDMap tmp;
  tmp.ip = 0;
  return tmp;
}

/* returns m successors including or after the number id
 */
vector<Chord::IDMap>
LocTable::succs(ConsistentHash::CHID id, unsigned int m, int status)
{
  vector<Chord::IDMap> v;
  v.clear();

  assert (ring.repok ());

  if (m <= 0) return v;

  idmapwrap *ptr = ring.closestsucc(id);
  assert(ptr);
  idmapwrap *ptrnext;

  uint j = 0;
  while (j < m) {
    if (ptr->n.ip == me.ip) break;

    ptrnext = ring.next(ptr);
    if (!ptrnext) ptrnext = ring.first();

    if (ptr->status <= status) {

      if ((id == (me.id+1)) && (!ptr->is_succ)) return v;
      if (v.size() > 0) 
	assert(ptr->n.ip != v[v.size()-1].ip);
      v.push_back(ptr->n);
      j++;
      if (j >= ring.size()) return v;
    }
    ptr = ptrnext;
  }
  return v;
}

Chord::IDMap
LocTable::pred(Chord::CHID id, int status)
{
  vector<Chord::IDMap> v = preds(id, 1, status);
  if (v.size() > 0) {
    return v[0];
  }

  Chord::IDMap tmp;
  tmp.ip = 0;
  return tmp;
}

vector<Chord::IDMap>
LocTable::preds(Chord::CHID id, uint m, int status, double to) 
{
  vector<Chord::IDMap> v;
  v.clear();

  assert (ring.repok ());
  idmapwrap *elm = ring.closestpred(id);

  assert(elm);
  idmapwrap *elmprev;
  while (elm->id!=me.id) {
    if ((elm->status <= status) && 
	(to < 0.0000001 || elm->is_succ 
	 || ((now()-elm->n.timestamp) < MINTIMEOUT)
	 || ((double)elm->n.alivetime/(double)(elm->n.alivetime+now()-elm->n.timestamp)) > to)) { 
      v.push_back(elm->n);
      if (v.size() == m) break;
    }
    elm = ring.prev(elm);
    if (!elm) elm = ring.last();
  }

  if (v.size() < m && to > 0.00000001) {
    elm = ring.closestpred(id);
    while (elm->id != me.id) {
      if ((elm->status <= status) && ((double)(elm->n.alivetime+now()-elm->n.timestamp)) < to){
	v.push_back(elm->n);
	if (v.size() == m) break;
      }
      elm = ring.prev(elm);
      if (!elm) elm = ring.last();
    }
  }
  return v;
}

/*
vector<Chord::IDMap>
LocTable::preds(Chord::CHID id, uint m, int status, Time expire) 
{
  vector<Chord::IDMap> v;
  v.clear();

  assert (ring.repok ());
  idmapwrap *elm = ring.closestpred(id);

  assert(elm);
  idmapwrap *elmprev;
  while (elm->id!=me.id) {
    if ((elm->status <= status) && 
	(!expire || elm->is_succ || (now()-elm->n.timestamp) < expire)) { 
      v.push_back(elm->n);
      if (v.size() == m) break;
    }
    elm = ring.prev(elm);
    if (!elm) elm = ring.last();
  }

  if (v.size() < m && expire) {
    elm = ring.closestpred(id);
    while (elm->id != me.id) {
      if ((elm->status <= status) && (now()-elm->n.timestamp) > expire){
	v.push_back(elm->n);
	if (v.size() == m) break;
      }
      elm = ring.prev(elm);
      if (!elm) elm = ring.last();
    }
  }
  return v;
}
*/
void
LocTable::print ()
{
  idmapwrap *m = ring.search(me.id);
  assert(m);                         
  printf ("ring:\n");
  idmapwrap *i = m;
  do {
    printf ("  %5u,%16qx\n", i->n.ip, i->n.id);
    i = ring.next(i);
    if (!i) i = ring.first();
  }while (i != m);
}

int
LocTable::add_check(Chord::IDMap n)
{
  idmapwrap *elm = ring.search(n.id);
  
  
  if (!elm) 
    return -1;

  if (elm->status <= LOC_HEALTHY) { 
    if (n.timestamp >= elm->n.timestamp) {
      elm->n.timestamp = n.timestamp;
      elm->status = LOC_ONCHECK;
      return LOC_ONCHECK;
    } else {
      return elm->status;
    }
  }else{
    return LOC_DEAD;
  }
}

bool 
LocTable::update_ifexists(Chord::IDMap n, bool replacement)
{
  idmapwrap *ptr = ring.search(n.id);
  if (!ptr) return false;
  ptr->n = n;
  ptr->n.timestamp = now();
  if (replacement)
    ptr->status= LOC_REPLACEMENT;
  else
    ptr->status = LOC_HEALTHY;
  return true;
}

bool
LocTable::add_node(Chord::IDMap n, bool is_succ, bool assertadd, Chord::CHID fs,Chord::CHID fe, bool replacement)
{
  Chord::IDMap succ1; 
  Chord::IDMap pred1; 

  if (!n.ip) {
    if (p2psim_verbose>=4)
      cout << " add_node wierd " << n.ip << endl;
    return false;
  }

  if (n.ip == me.ip)
    return false;

  if (vis) {
    succ1 = succ(me.id+1);
    pred1 = pred(me.id-1);
  }
  idmapwrap *elm = ring.closestsucc(n.id);
  if (elm && elm->id == n.id) {
    if (replacement && elm->status == LOC_HEALTHY)
	elm->status = LOC_REPLACEMENT;
    if (n.timestamp > elm->n.timestamp) {
      elm->n = n;
      if (replacement)
	elm->status = LOC_REPLACEMENT;
      else
	elm->status = LOC_HEALTHY;
    }
    if (is_succ) {
      elm->fs = elm->fe = 0;
      elm->is_succ = is_succ;
    }
    elm->fs = fs;
    elm->fe = fe;
    return false;
  } else {
    idmapwrap *newelm = New idmapwrap(n);
    if (elm && elm->is_succ) {
      newelm->is_succ = true;
    } else {
      newelm->is_succ = is_succ;
      if (is_succ) {
	elm = ring.prev(elm);
	if (!elm) elm = ring.last();
	while (elm->n.ip!=me.ip && !elm->is_succ) {
	  elm->is_succ = true;
	  elm = ring.prev(elm);
	  if (!elm) elm = ring.last();
	}
      }
    }
    newelm->fs = fs;
    newelm->fe = fe;
    newelm->status = replacement? LOC_REPLACEMENT:LOC_HEALTHY;
    if (ring.insert(newelm)) {
    }else{
      abort();
    }
    return true;
  }
}

bool
LocTable::del_node(Chord::IDMap n, bool force)
{
  assert(n.ip != me.ip);
  idmapwrap *elm = ring.search(n.id);
  if (!elm) return false;
  if (!force) {
    if (n.timestamp > elm->n.timestamp)
      elm->n.timestamp = n.timestamp;
    elm->status = LOC_DEAD;
  } else {
    elm = ring.remove(n.id);
    bzero(elm,sizeof(*elm));
    delete elm;
  }
  assert (ring.repok ());
  return true;
}

uint
LocTable::size(uint status, double to)
{
  if (status == LOC_DEAD)
    return ring.size();
  idmapwrap *elm = ring.first();
  uint sz = 0;
  while (elm) {
    double ti = (double)elm->n.alivetime/(double)(now()-elm->n.timestamp+elm->n.alivetime);
    if ((elm->status <= status) && (to<0.0000001 
	  || elm->is_succ 
	  || (!elm->n.alivetime)
	  || ((now()-elm->n.timestamp) < MINTIMEOUT)
	  || (ti> to))) {
      sz++;
    }
    elm = ring.next(elm);
  }
  return sz;
}


vector<Chord::IDMap>
LocTable::next_hops(Chord::CHID key, uint nsz)
{
  return preds(key, nsz, LOC_HEALTHY);
}

Chord::IDMap
LocTable::next_hop(Chord::CHID key)
{
  vector<Chord::IDMap> v = next_hops(key, 1);

  if (v.size() == 0) 
    return me;

  return v[0];
}

vector<Chord::IDMap>
LocTable::get_all(uint status)
{
  vector<Chord::IDMap> v;
  v.clear();

  idmapwrap *currp; 
  currp = ring.first();
  while (currp) {
    if (currp->status <= status) {
      v.push_back(currp->n);
    }
    currp = ring.next(currp);
  }
  return v;
}

//for debugging purpose
Chord::IDMap
LocTable::first()
{
  idmapwrap *elm = ring.first();
  return elm->n;
}

Chord::IDMap
LocTable::last()
{
  idmapwrap *elm = ring.last();
  return elm->n;
}

Chord::IDMap
LocTable::search(ConsistentHash::CHID id)
{
  idmapwrap *elm = ring.search(id);
  assert(elm);
  return elm->n;
}

void
LocTable::last_succ(Chord::IDMap n)
{
  if (n.ip == me.ip)
    return;
  idmapwrap *elm = ring.closestsucc(n.id+1);
  while ((elm->is_succ) && (me.ip != elm->n.ip)){
    elm->is_succ = false;
    elm = ring.next(elm);
    if (!elm) elm = ring.first();
  }
  if (me.ip == elm->n.ip)
    elm->is_succ = false;
}

bool
LocTable::is_succ(Chord::IDMap n)
{
  idmapwrap *elm = ring.search(n.id);
  return (elm && elm->is_succ);
}

uint
LocTable::succ_size()
{
  idmapwrap *elm = ring.first();
  uint n = 0;
  while (elm) {
    if ((elm->is_succ) && (elm->status <= LOC_HEALTHY))
      n++;
    elm = ring.next(elm);
  }
  return n;
}

uint
LocTable::live_size(double to)
{
  idmapwrap *elm = ring.first();
  uint n = 0;
  while (elm) {
    if (elm->status <= LOC_HEALTHY && elm->n.ip && Network::Instance()->alive(elm->n.ip)
	&& (to<0.0000001 
	  || elm->is_succ 
	  || !elm->n.alivetime
	  || (now()-elm->n.timestamp < MINTIMEOUT)
	  || ((double)elm->n.alivetime/(double)(now()-elm->n.timestamp+elm->n.alivetime)>to)))
      n++;
    elm = ring.next(elm);
  }
  return n;
}

int
LocTable::find_node(Chord::IDMap n)
{
  idmapwrap *elm = ring.closestsucc(n.id);
  if (elm->n.ip == n.ip && elm->n.timestamp >= n.timestamp) 
    return elm->status;
  else 
    return -1;
}

void
LocTable::dump()
{
  printf("===%u,%qx loctable dump at %llu===\n", me.ip, me.id,now());
  idmapwrap *elm = ring.closestsucc(me.id+1);
  while (elm->n.ip != me.ip) {
    printf("(%qx, %u, %d, %llu)\n", elm->n.id, elm->n.ip, elm->is_succ, elm->n.timestamp);
    elm = ring.next(elm);
    if (!elm) elm = ring.first();
  }
  
}
void
LocTable::stat()
{
  Time t = now();
  Chord::IDMap succ;
  succ.ip = 0;
  uint num_succ = 0;
  uint num_finger = 0;
  idmapwrap *elm = ring.closestsucc(me.id+1);
  while (elm->n.ip != me.ip) {
    if (!succ.ip) succ = elm->n;
    if (elm->is_succ) 
      num_succ++;
    else
      num_finger++;
    elm = ring.next(elm);
    if (!elm) elm = ring.first();
  }
  printf("%llu loctable stat for (%u,%qx): succ %u,%qx number of succs %u number of finger %u\n", 
      t, me.ip, me.id, succ.ip, succ.id, num_succ, num_finger);
}

void
LocTable::rand_sample(Chord::IDMap &askwhom, Chord::IDMap &start, Chord::IDMap &end)
{
  double x = random()/(double)(RAND_MAX);
  ConsistentHash::CHID samp = (ConsistentHash::CHID) (x * (ConsistentHash::CHID)(-1));
  idmapwrap *elm = ring.closestsucc(samp);
  idmapwrap *elmtmp = elm;

  while (elm->status > LOC_HEALTHY) {
    elm = ring.next(elm);
    if (!elm) elm = ring.first();
  }
  start = elm->n;
  do {
    elm = ring.next(elm);
    if (!elm) elm = ring.first();
  } while (elm->status > LOC_HEALTHY);
  end = elm->n;

  askwhom = start;
  //XXX jinyang: this is an ugly hack, budget should be included as part of the IDMap field
  uint prev_budget = ((Accordion *)Network::Instance()->getnode(askwhom.ip))->budget();
  ConsistentHash::CHID gap = ConsistentHash::distance(start.id,end.id);
  uint i = 0;
  while (i < 10) {
    elmtmp = ring.prev(elmtmp);
    if (!elmtmp) elmtmp = ring.last();
    if (elmtmp->n.ip == me.ip)
      break;
    if (elmtmp->status <= LOC_HEALTHY) {
      double r1 = 1.0 + (double)ConsistentHash::distance(askwhom.id,elmtmp->n.id)/(double)gap; 
      double r2 = (double)prev_budget/(double)((Accordion *)Network::Instance()->getnode(elmtmp->n.ip))->budget();
      if (r1 < r2) {
	askwhom = elmtmp->n;
	prev_budget = ((Accordion *)Network::Instance()->getnode(elmtmp->n.ip))->budget();
      }
      i++;
    }
  }
  uint my_budget = ((Accordion *)Network::Instance()->getnode(me.ip))->budget();
  if (my_budget > prev_budget) {
    double rr = (double)random()/(double)RAND_MAX;
    if (rr > ((double)prev_budget/(double)my_budget)) 
      askwhom = me; //don't send this exploration packet
  }
}

uint
LocTable::sample_smallworld(uint est_n, Chord::IDMap &askwhom, Chord::IDMap &start, Chord::IDMap &end, double tt, ConsistentHash::CHID mingap)
{
  //use LOC_REPLACEMENT 
  //to denote that the finger's succeeding gap is full
  uint op = 0;
  if (lastfull && (now()-lastfull) < 2*MINTIMEOUT) {
    rand_sample(askwhom,start,end);
  }else{
    //get a good sample
    double x = random()/(