routert.cc

Click is a modular router toolkit. To use it you ll need to know how to compile and install the sof

// -*- c-basic-offset: 4 -*-
/*
 * routert.{cc,hh} -- tool definition of router
 * Eddie Kohler
 *
 * Copyright (c) 1999-2000 Massachusetts Institute of Technology
 * Copyright (c) 2000 Mazu Networks, Inc.
 * Copyright (c) 2001 International Computer Science Institute
 * Copyright (c) 2007 Regents of the University of California
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, subject to the conditions
 * listed in the Click LICENSE file. These conditions include: you must
 * preserve this copyright notice, and you cannot mention the copyright
 * holders in advertising related to the Software without their permission.
 * The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
 * notice is a summary of the Click LICENSE file; the license in that file is
 * legally binding.
 */

#include <click/config.h>

#include "routert.hh"
#include "eclasst.hh"
#include "elementmap.hh"
#include "processingt.hh"
#include <click/bitvector.hh>
#include <click/confparse.hh>
#include <click/straccum.hh>
#include <click/variableenv.hh>
#include <stdio.h>

RouterT::RouterT()
    : ElementClassT("<router>"),
      _element_name_map(-1), _free_element(0), _n_live_elements(0),
      _new_eindex_collector(0),
      _free_conn(-1),
      _declared_type_map(-1),
      _archive_map(-1),
      _declaration_scope(0), _scope_cookie(0),
      _scope(0),
      _nformals(0), _ninputs(0), _noutputs(0), _scope_order_error(false),
      _circularity_flag(false), _overload_type(0)
{
}

RouterT::RouterT(const String &name, const LandmarkT &landmark, RouterT *declaration_scope)
    : ElementClassT(name),
      _element_name_map(-1), _free_element(0), _n_live_elements(0),
      _new_eindex_collector(0),
      _free_conn(-1),
      _declared_type_map(-1),
      _archive_map(-1),
      _declaration_scope(declaration_scope), _scope_cookie(0),
      _scope(declaration_scope ? &declaration_scope->_scope : 0),
      _nformals(0), _ninputs(0), _noutputs(0), _scope_order_error(false),
      _circularity_flag(false), _overload_type(0), _type_landmark(landmark)
{
    // borrow definitions from 'declaration'
    if (_declaration_scope) {
	_declaration_scope_cookie = _declaration_scope->_scope_cookie;
	_declaration_scope->_scope_cookie++;
	_declaration_scope->use();
    }
    // create input and output pseudoelements
    get_element("input", ElementClassT::tunnel_type(), String(), landmark);
    get_element("output", ElementClassT::tunnel_type(), String(), landmark);
    *(_traits.component(Traits::D_CLASS)) = name;
}

RouterT::~RouterT()
{
    for (int i = 0; i < _elements.size(); i++)
	delete _elements[i];
    if (_overload_type)
	_overload_type->unuse();
    if (_declaration_scope)
	_declaration_scope->unuse();
}

void
RouterT::check() const
{
    int ne = nelements();
    int nc = nconnections();
    int nt = _declared_types.size();

    // check basic sizes
    assert(_elements.size() == _first_conn.size());

    // check element type names
    int nt_found = 0;
    for (StringMap::const_iterator iter = _declared_type_map.begin(); iter.live(); iter++) {
	int sc = _scope_cookie;
	for (int i = iter.value(); i >= 0; i = _declared_types[i].prev_name) {
	    assert(_declared_types[i].name() == iter.key());
	    assert(_declared_types[i].prev_name < i);
	    assert(_declared_types[i].scope_cookie <= sc);
	    sc = _declared_types[i].scope_cookie - 1;
	    nt_found++;
	}
    }
    // note that nt_found might not equal nt, because of anonymous classes

    // check element types
    HashTable<ElementClassT *, int> type_map(-1);
    for (int i = 0; i < nt; i++) {
	assert(type_map[_declared_types[i].type] < 0);
	type_map.set(_declared_types[i].type, i);
    }

    // check element names
    for (StringMap::const_iterator iter = _element_name_map.begin(); iter.live(); iter++) {
	String key = iter.key();
	int value = iter.value();
	if (value >= 0)
	    assert(value < ne && _elements[value]->name() == key); // && _elements[value].live());
    }

    // check free elements
    for (ElementT *e = _free_element; e; e = e->tunnel_input()) {
	assert(e->dead());
	assert(_elements[e->eindex()] == e);
    }

    // check elements
    for (int i = 0; i < ne; i++) {
	const ElementT *e = _elements[i];
	assert(e->router() == this);
	if (e->live() && e->tunnel_input())
	    assert(e->tunnel() && e->tunnel_input()->tunnel_output() == e);
	if (e->live() && e->tunnel_output())
	    assert(e->tunnel() && e->tunnel_output()->tunnel_input() == e);
    }

    // check hookup
    for (int i = 0; i < nc; i++)
	if (connection_live(i))
	    assert(has_connection(_conn[i].from(), _conn[i].to()));

    // check hookup next pointers, port counts
    for (int i = 0; i < ne; i++)
	if (_elements[i]->live()) {
	    int ninputs = 0, noutputs = 0;
	    const ElementT *e = element(i);

	    int j = _first_conn[i][end_from];
	    while (j >= 0) {
		assert(j < _conn.size());
		assert(_conn[j].from_element() == e);
		if (_conn[j].from().port >= noutputs)
		    noutputs = _conn[j].from().port + 1;
		j = _conn[j].next_from();
	    }

	    j = _first_conn[i][end_to];
	    while (j >= 0) {
		assert(j < _conn.size());
		assert(_conn[j].to_element() == e && connection_live(j));
		if (_conn[j].to().port >= ninputs)
		    ninputs = _conn[j].to().port + 1;
		j = _conn[j].next_to();
	    }

	    assert(ninputs == e->ninputs() && noutputs == e->noutputs());
	}

    // check free hookup pointers
    Bitvector bv(_conn.size(), true);
    for (int i = _free_conn; i >= 0; i = _conn[i].next_from()) {
	assert(i >= 0 && i < _conn.size());
	assert(bv[i]);
	bv[i] = false;
    }
    for (int i = 0; i < _conn.size(); i++)
	assert(connection_live(i) == (bool)bv[i]);
}


ElementT *
RouterT::add_element(const ElementT &elt_in)
{
    int i;
    _n_live_elements++;
    ElementT *elt = new ElementT(elt_in);
    if (_free_element) {
	i = _free_element->eindex();
	_free_element = _free_element->tunnel_input();
	delete _elements[i];
	_first_conn[i] = Pair(-1, -1);
    } else {
	i = _elements.size();
	_elements.push_back(0);
	_first_conn.push_back(Pair(-1, -1));
    }
    if (_new_eindex_collector)
	_new_eindex_collector->push_back(i);
    _elements[i] = elt;
    elt->_eindex = i;
    elt->_owner = this;
    return elt;
}

ElementT *
RouterT::get_element(const String &name, ElementClassT *type,
		     const String &config, const LandmarkT &landmark)
{
    int &i = _element_name_map[name];
    if (i >= 0)
	return _elements[i];
    else {
	ElementT *e = add_element(ElementT(name, type, config, landmark));
	i = e->eindex();
	return e;
    }
}

ElementT *
RouterT::add_anon_element(ElementClassT *type, const String &config,
			  const LandmarkT &landmark)
{
    String name = ";" + type->name() + "@" + String(_n_live_elements + 1);
    ElementT *result = add_element(ElementT(name, type, config, landmark));
    assign_element_name(result->eindex());
    return result;
}

void
RouterT::change_ename(int ei, const String &new_name)
{
    assert(ElementT::name_ok(new_name));
    ElementT &e = *_elements[ei];
    if (e.live()) {
	if (eindex(e.name()) == ei)
	    _element_name_map.set(e.name(), -1);
	e._name = new_name;
	_element_name_map.set(new_name, ei);
    }
}

void
RouterT::assign_element_name(int ei)
{
    assert(_elements[ei]->anonymous());
    String name = _elements[ei]->name().substring(1);
    if (eindex(name) >= 0) {
	int at_pos = name.find_right('@');
	assert(at_pos >= 0);
	String prefix = name.substring(0, at_pos + 1);
	int anonymizer;
	cp_integer(name.substring(at_pos + 1), &anonymizer);
	do {
	    anonymizer++;
	    name = prefix + String(anonymizer);
	} while (eindex(name) >= 0);
    }
    change_ename(ei, name);
}

void
RouterT::deanonymize_elements()
{
    for (int i = 0; i < _elements.size(); i++)
	if (_elements[i]->anonymous())
	    assign_element_name(i);
}


//
// TYPES
//

ElementClassT *
RouterT::locally_declared_type(const String &name) const
{
    int i = _declared_type_map[name];
    return (i >= 0 ? _declared_types[i].type : 0);
}

ElementClassT *
RouterT::declared_type(const String &name, int scope_cookie) const
{
    for (const RouterT *r = this; r; scope_cookie = r->_declaration_scope_cookie, r = r->_declaration_scope)
	for (int i = r->_declared_type_map[name]; i >= 0; i = r->_declared_types[i].prev_name)
	    if (r->_declared_types[i].scope_cookie <= scope_cookie)
		return r->_declared_types[i].type;
    return 0;
}

void
RouterT::add_declared_type(ElementClassT *ec, bool anonymous)
{
    assert(ec);
    if (anonymous || !ec->name())
	_declared_types.push_back(ElementType(ec, _scope_cookie, -1));
    else if (locally_declared_type(ec->name()) != ec) {
	int prev = _declared_type_map[ec->name()];
	if (prev >= 0)		// increment scope_cookie if redefining class
	    _scope_cookie++;
	_declared_types.push_back(ElementType(ec, _scope_cookie, prev));
	_declared_type_map.set(ec->name(), _declared_types.size() - 1);
    }
}

void
RouterT::collect_types(HashTable<ElementClassT *, int> &m) const
{
    HashTable<ElementClassT *, int>::iterator it = m.find_insert(const_cast<RouterT *>(this), 0);
    if (it.value() == 0) {
	it.value() = 1;
	for (int i = 0; i < _declared_types.size(); i++)
	    _declared_types[i].type->collect_types(m);
	for (int i = 0; i < _elements.size(); i++)
	    _elements[i]->type()->collect_types(m);
	if (_overload_type)
	    _overload_type->collect_types(m);
    }
}

void
RouterT::collect_locally_declared_types(Vector<ElementClassT *> &v) const
{
    for (Vector<ElementType>::const_iterator i = _declared_types.begin(); i != _declared_types.end(); i++)
	v.push_back(i->type);
}

void
RouterT::collect_overloads(Vector<ElementClassT *> &v) const
{
    if (_overload_type)
	_overload_type->collect_overloads(v);
    v.push_back(const_cast<RouterT *>(this));
}


//
// CONNECTIONS
//

void
RouterT::update_noutputs(int e)
{
    int n = 0;
    for (int i = _first_conn[e][end_from]; i >= 0; i = _conn[i].next_from())
	if (_conn[i].from().port >= n)
	    n = _conn[i].from().port + 1;
    _elements[e]->set_noutputs(n);
}

void
RouterT::update_ninputs(int e)
{
    int n = 0;
    for (int i = _first_conn[e][end_to]; i >= 0; i = _conn[i].next_to())
	if (_conn[i].to().port >= n)
	    n = _conn[i].to().port + 1;
    _elements[e]->set_ninputs(n);
}

bool
RouterT::add_connection(const PortT &hfrom, const PortT &hto,
			const LandmarkT &landmark)
{
    assert(hfrom.router() == this && hfrom.element->live()
	   && hto.router() == this && hto.element->live());

    Pair &first_from = _first_conn[hfrom.eindex()];
    Pair &first_to = _first_conn[hto.eindex()];

    int i;
    if (_free_conn >= 0) {
	i = _free_conn;
	_free_conn = _conn[i].next_from();
	_conn[i] = ConnectionT(hfrom, hto, landmark, first_from[end_from], first_to[end_to]);
    } else {
	i = _conn.size();
	_conn.push_back(ConnectionT(hfrom, hto, landmark, first_from[end_from], first_to[end_to]));
    }

    first_from[end_from] = first_to[end_to] = i;

    // maintain port counts
    if (hfrom.port >= hfrom.element->noutputs())
	hfrom.element->set_noutputs(hfrom.port + 1);
    if (hto.port >= hto.element->ninputs())
	hto.element->set_ninputs(hto.port + 1);

    return true;
}

void
RouterT::compact_connections()
{
    int nc = _conn.size();
    Vector<int> new_numbers(nc, -1);
    int last = nc;
    for (int i = 0; i < last; i++)
	if (connection_live(i))
	    new_numbers[i] = i;
	else {
	    for (last--; last > i && !connection_live(last); last--)
		/* nada */;
	    if (last > i)
		new_numbers[last] = i;
	}

    if (last == nc)
	return;

    for (int i = 0; i < nc; i++)
	if (new_numbers[i] >= 0 && new_numbers[i] != i)
	    _conn[ new_numbers[i] ] = _conn[i];

    _conn.resize(last);
    for (int i = 0; i < last; i++) {
	ConnectionT &c = _conn[i];
	if (c._next[end_from] >= 0)
	    c._next[end_from] = new_numbers[c._next[end_from]];
	if (c._next[end_to] >= 0)
	    c._next[end_to] = new_numbers[c._next[end_to]];
    }

    int ne = nelements();
    for (int i = 0; i < ne; i++) {
	Pair &n = _first_conn[i];
	if (n[end_from] >= 0)
	    n[end_from] = new_numbers[n[end_from]];
	if (n[end_to] >= 0)
	    n[end_to] = new_numbers[n[end_to]];
    }

    _free_conn = -1;
}

void
RouterT::unlink_connection_from(int c)
{
    int e = _conn[c].from_eindex();
    int port = _conn[c].from_port();

    // find previous connection
    int prev = -1;
    int trav = _first_conn[e][end_from];
    while (trav >= 0 && trav != c) {
	prev = trav;
	trav = _conn[trav].next_from();
    }
    assert(trav == c);

    // unlink this connection
    if (prev < 0)
	_first_conn[e][end_from] = _conn[trav].next_from();
    else
	_conn[prev]._next[end_from] = _conn[trav].next_from();