iprw.cc

COPE the first practical network coding scheme which is developped on click

	uint32_t val = (_sequential ? _next_variation : random() & _variation_mask);
	uint32_t step = (_sequential ? 1 : random() | 1);
	uint32_t base = (_is_napt ? ntohs(_sport) : ntohl(_saddr.addr()));
	IPFlowID lookup = out.rev();
	for (uint32_t count = 0; count <= _variation_mask; count++, val = (val + step) & _variation_mask)
	    if (val <= _variation_top) {
		if (_is_napt)
		    lookup.set_dport(htons(base + val));
		else
		    lookup.set_daddr(htonl(base + val));
		if (!rev_map.findp(lookup)) {
		    if (_is_napt)
			out.set_sport(lookup.dport());
		    else
			out.set_saddr(lookup.daddr());
		    _next_variation = val + 1;
		    goto found;
		}
	    }
	return false;
    }

  found:
    Mapping::make_pair(ip_p, in, out, fport, rport, fmap, rmap);
    accept_mapping(fmap);
    return true;
}

void
IPRw::Pattern::accept_mapping(Mapping *m)
{
    m->_pat = this;
    _nmappings++;
}

inline void
IPRw::Pattern::mapping_freed(Mapping *)
{
    _nmappings--;
}

String
IPRw::Pattern::unparse() const
{
    StringAccum sa;
    if (!_is_napt && _variation_top)
	sa << _saddr << '-'
	   << IPAddress(htonl(ntohl(_saddr.addr()) + _variation_top));
    else if (_saddr)
	sa << _saddr;
    else
	sa << '-';

    if (!_is_napt)
	/* nada */;
    else if (!_sport)
	sa << " -";
    else if (_variation_top)
	sa << ' ' << ntohs(_sport) << '-' << (ntohs(_sport) + _variation_top);
    else
	sa << ' ' << ntohs(_sport);

    if (_daddr)
	sa << ' ' << _daddr;
    else
	sa << " -";

    if (!_is_napt)
	/* nada */;
    else if (!_dport)
	sa << " -";
    else
	sa << ' ' << ntohs(_dport);

    sa << " [" << _nmappings << ']';

    return sa.take_string();
}

//
// IPMapper
//

void
IPMapper::notify_rewriter(IPRw *, ErrorHandler *)
{
}

IPRw::Mapping *
IPMapper::get_map(IPRw *, int, const IPFlowID &, Packet *)
{
    return 0;
}

//
// IPRw
//

IPRw::IPRw()
{
}

IPRw::~IPRw()
{
}

int
IPRw::notify_pattern(Pattern *p, ErrorHandler *)
{
    for (int i = 0; i < _all_patterns.size(); i++)
	if (_all_patterns[i] == p)
	    return 0;
    _all_patterns.push_back(p);
    return 0;
}


int
IPRw::parse_input_spec(const String &line, InputSpec &is,
		       String name, ErrorHandler *errh)
{
    PrefixErrorHandler cerrh(errh, name + ": ");
    String word, rest;
    if (!cp_word(line, &word, &rest))
	return cerrh.error("empty argument");
    cp_eat_space(rest);
  
    is.kind = INPUT_SPEC_DROP;
  
    if (word == "pass" || word == "passthrough" || word == "nochange") {
	int32_t outnum = 0;
	if (rest && !cp_integer(rest, &outnum))
	    return cerrh.error("syntax error, expected 'nochange [OUTPUT]'");
	else if (outnum < 0 || outnum >= noutputs())
	    return cerrh.error("output port out of range");
	is.kind = INPUT_SPEC_NOCHANGE;
	is.u.output = outnum;
    
    } else if (word == "keep") {
	if (cp_va_space_parse(rest, this, ErrorHandler::silent_handler(),
			      cpUnsigned, "forward output", &is.u.pattern.fport,
			      cpUnsigned, "reverse output", &is.u.pattern.rport,
			      cpEnd) < 0)
	    return cerrh.error("syntax error, expected 'keep FOUTPUT ROUTPUT'");
	if (is.u.pattern.fport >= noutputs() || is.u.pattern.rport >= noutputs())
	    return cerrh.error("output port out of range");
	is.kind = INPUT_SPEC_KEEP;
	is.u.pattern.p = 0;
    
    } else if (word == "drop") {
	if (rest)
	    return cerrh.error("syntax error, expected 'drop'");
    
    } else if (word == "pattern") {
	if (Pattern::parse_with_ports(rest, &is.u.pattern.p, &is.u.pattern.fport, &is.u.pattern.rport, this, &cerrh) < 0)
	    return -1;
	if (is.u.pattern.fport >= noutputs() || is.u.pattern.rport >= noutputs())
	    return cerrh.error("output port out of range");
	is.u.pattern.p->use();
	is.kind = INPUT_SPEC_PATTERN;
	if (notify_pattern(is.u.pattern.p, &cerrh) < 0)
	    return -1;
    
    } else if (Element *e = cp_element(word, this, 0)) {
	IPMapper *mapper = (IPMapper *)e->cast("IPMapper");
	if (rest)
	    return cerrh.error("syntax error, expected 'ELEMENTNAME'");
	else if (!mapper)
	    return cerrh.error("element is not an IPMapper");
	else {
	    is.kind = INPUT_SPEC_MAPPER;
	    is.u.mapper = mapper;
	    mapper->notify_rewriter(this, &cerrh);
	}
    
    } else
	return cerrh.error("unknown specification");
  
    return 0;
}


inline IPRw::Mapping *
IPRw::Mapping::free_from_list(Map &map, bool notify)
{
    // see also clear_map below
    //click_chatter("kill %s", reverse()->flow_id().rev().s().cc());
    Mapping *next = _free_next;
    if (notify && _pat)
	_pat->mapping_freed(primary());
    map.remove(reverse()->flow_id().rev());
    map.remove(flow_id().rev());
    delete reverse();
    delete this;
    return next;
}

void
IPRw::take_state_map(Map &map, Mapping **free_head, Mapping **free_tail,
		     const Vector<Pattern *> &in_patterns,
		     const Vector<Pattern *> &out_patterns)
{
    Mapping *to_free = 0;
    int np = in_patterns.size();
    int no = noutputs();
  
    for (Map::iterator iter = map.begin(); iter; iter++) {
	Mapping *m = iter.value();
	if (m->is_primary()) {
	    Pattern *p = m->pattern(), *q = 0;
	    for (int i = 0; i < np; i++)
		if (in_patterns[i] == p) {
		    q = out_patterns[i];
		    break;
		}
	    if (p)
		p->mapping_freed(m);
	    if (q && m->output() < no && m->reverse()->output() < no) {
		q->accept_mapping(m);
		if (m->free_tracked()) {
		    if (free_head)
			m->append_to_free(*free_head, *free_tail);
		    else
			m->clear_free_tracked();
		}
	    } else {
		m->set_free_next(to_free);
		to_free = m;
	    }
	}
    }

    while (to_free)
	to_free = to_free->free_from_list(map, false);
}

void
IPRw::clean_map(Map &table, uint32_t last_jif)
{
    //click_chatter("cleaning map");
    Mapping *to_free = 0;

    for (Map::iterator iter = table.begin(); iter; iter++)
	if (Mapping *m = iter.value()) {
	    if (m->is_primary() && !m->used_since(last_jif) && !m->free_tracked()) {
		m->set_free_next(to_free);
		to_free = m;
	    }
	}

    while (to_free)
	to_free = to_free->free_from_list(table, true);
}

void
IPRw::clean_map_free_tracked(Map &table,
			     Mapping *&free_head, Mapping *&free_tail,
			     uint32_t last_jif)
{
    Mapping *free_list = free_head;
    Mapping **prev_ptr = &free_list;

    Mapping *m = free_list;
    while (m) {
	Mapping *next = m->free_next();
	if (!m->session_over()) {
	    // reuse of a port; take it off the free-tracked list
	    *prev_ptr = next;
	    m->clear_free_tracked();
	} else if (m->used_since(last_jif))
	    break;
	else
	    prev_ptr = &m->_free_next;
	m = next;
    }

    // cut off free_list before 'm'
    *prev_ptr = 0;

    // move free_head forward, to 'm' or beyond
    if (m && m->free_next()) {
	// if 'm' exists, then shift it to the end of the list
	free_head = m->free_next();
	m->set_free_next(0);
	m->append_to_free(free_head, free_tail);
    } else
	free_head = free_tail = m;

    // free contents of free_list
    while (free_list)
	free_list = free_list->free_from_list(table, true);
}

void
IPRw::incr_clean_map_free_tracked(Map &table,
				  Mapping *&free_head, Mapping *&free_tail,
				  uint32_t last_jif)
{
    Mapping *m = free_head;
    if (!m->session_over()) {
	// has been recycled; remove from free-tracked list
	free_head = m->free_next();
	if (!free_head)
	    free_tail = 0;
	m->clear_free_tracked();
    } else if (m->used_since(last_jif)) {
	// recently used; cycle to end of list
	if (m->free_next()) {
	    free_head = m->free_next();
	    m->set_free_next(0);
	    m->append_to_free(free_head, free_tail);
	}
    } else {
	// actually free; delete it
	free_head = m->free_from_list(table, true);
	if (!free_head)
	    free_tail = 0;
    }
}

void
IPRw::clear_map(Map &table)
{
    Mapping *to_free = 0;

    for (Map::iterator iter = table.begin(); iter; iter++) {
	Mapping *m = iter.value();
	if (m->is_primary()) {
	    m->set_free_next(to_free);
	    to_free = m;
	}
    }

    while (to_free) {
	// don't call free_from_list, because there is no need to update
	// 'table' incrementally
	Mapping *next = to_free->free_next();
	if (Pattern *pat = to_free->pattern())
	    pat->mapping_freed(to_free);
	delete to_free->reverse();
	delete to_free;
	to_free = next;
    }

    table.clear();
}

ELEMENT_PROVIDES(IPRw)

#include <click/bighashmap.cc>
#include <click/vector.cc>
#if EXPLICIT_TEMPLATE_INSTANCES
template class HashMap<IPFlowID, IPRw::Mapping *>;
template class HashMapIterator<IPFlowID, IPRw::Mapping *>;
template class Vector<IPRw::InputSpec>;
#endif
CLICK_ENDDECLS