processingt.cc

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

// -*- c-basic-offset: 4 -*-
/*
 * processingt.{cc,hh} -- decide on a Click configuration's processing
 * Eddie Kohler
 *
 * Copyright (c) 2000 Massachusetts Institute of Technology
 * Copyright (c) 2001 International Computer Science Institute
 *
 * 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 "processingt.hh"
#include <click/error.hh>
#include <click/bitvector.hh>
#include <click/straccum.hh>
#include "elementmap.hh"
#include <string.h>

const char ProcessingT::processing_letters[] = "ahl";

ProcessingT::ProcessingT()
    : _router(0)
{
}

ProcessingT::ProcessingT(const RouterT *r, ErrorHandler *errh)
    : _router(0)
{
    reset(r, ElementMap::default_map(), false, errh);
}

ProcessingT::ProcessingT(const RouterT *r, ElementMap *em, ErrorHandler *errh)
    : _router(0)
{
    reset(r, em, false, errh);
}

ProcessingT::ProcessingT(const RouterT *r, ElementMap *em, bool flatten,
			 ErrorHandler *errh)
    : _router(0)
{
    reset(r, em, flatten, errh);
}

void
ProcessingT::create_pidx(ErrorHandler *errh)
{
    int ne = _router->nelements();
    _input_pidx.assign(ne, 0);
    _output_pidx.assign(ne, 0);

    // count used input and output ports for each element
    int ci = 0, co = 0;
    for (int i = 0; i < ne; i++) {
	_input_pidx[i] = ci;
	_output_pidx[i] = co;
	ci += _router->element(i)->ninputs();
	co += _router->element(i)->noutputs();
    }
    _input_pidx.push_back(ci);
    _output_pidx.push_back(co);

    // create eidxes
    _input_elt.clear();
    _output_elt.clear();
    ci = 0, co = 0;
    for (int i = 1; i <= ne; i++) {
	const ElementT *e = _router->element(i - 1);
	for (; ci < _input_pidx[i]; ci++)
	    _input_elt.push_back(e);
	for (; co < _output_pidx[i]; co++)
	    _output_elt.push_back(e);
    }

    // complain about dead elements with live connections
    if (errh) {
	for (RouterT::const_iterator x = _router->begin_elements(); x; x++)
	    if (x->dead() && (x->ninputs() > 0 || x->noutputs() > 0))
		errh->lwarning(x->landmark(), "dead element %s has live connections", x->name_c_str());
    }
}

static int
next_processing_code(const String &str, int &pos, ErrorHandler *errh,
		     const String &landmark, ElementClassT *etype)
{
    const char *s = str.data();
    int len = str.length();
    if (pos >= len)
	return -2;

    switch (s[pos]) {

      case 'h': case 'H':
	pos++;
	return ProcessingT::VPUSH;
    
      case 'l': case 'L':
	pos++;
	return ProcessingT::VPULL;
	
      case 'a': case 'A':
	pos++;
	return ProcessingT::VAGNOSTIC;

      case '/':
	return -2;

      default:
	errh->lerror(landmark, "bad character '%c' in processing code for '%s'", s[pos], etype->printable_name_c_str());
	pos++;
	return -1;
    
    }
}

void
ProcessingT::initial_processing_for(int ei, ErrorHandler *errh)
{
    // don't handle uprefs or tunnels
    const ElementT *e = _router->element(ei);
    ElementClassT *etype = e->type();
    if (!etype || etype == ElementClassT::tunnel_type())
	return;

    String landmark = e->landmark();
    String pc = etype->traits().processing_code;
    if (!pc) {
	errh->lwarning(landmark, "'%s' has no processing code; assuming agnostic", etype->printable_name_c_str());
	return;
    }

    int pos = 0;
    int len = pc.length();

    int start_in = _input_pidx[ei];
    int start_out = _output_pidx[ei];

    int val = 0;
    int last_val = 0;
    for (int i = 0; i < e->ninputs(); i++) {
	if (last_val >= 0)
	    last_val = next_processing_code(pc, pos, errh, landmark, etype);
	if (last_val >= 0)
	    val = last_val;
	_input_processing[start_in + i] = val;
    }

    while (pos < len && pc[pos] != '/')
	pos++;
    if (pos >= len)
	pos = 0;
    else
	pos++;

    last_val = 0;
    for (int i = 0; i < e->noutputs(); i++) {
	if (last_val >= 0)
	    last_val = next_processing_code(pc, pos, errh, landmark, etype);
	if (last_val >= 0)
	    val = last_val;
	_output_processing[start_out + i] = val;
    }
}

void
ProcessingT::initial_processing(ErrorHandler *errh)
{
    _input_processing.assign(ninput_pidx(), VAGNOSTIC);
    _output_processing.assign(noutput_pidx(), VAGNOSTIC);
    for (int i = 0; i < nelements(); i++)
	initial_processing_for(i, errh);
}

void
ProcessingT::processing_error(const ConnectionT &conn, int processing_from,
			      ErrorHandler *errh)
{
  const char *type1 = (processing_from == VPUSH ? "push" : "pull");
  const char *type2 = (processing_from == VPUSH ? "pull" : "push");
  if (conn.landmark() == "<agnostic>")
    errh->lerror(conn.from_element()->landmark(),
		 "agnostic '%s' in mixed context: %s input %d, %s output %d",
		 conn.from_element()->name_c_str(), type2, conn.to_port(),
		 type1, conn.from_port());
  else
    errh->lerror(conn.landmark(),
		 "'%s' %s output %d connected to '%s' %s input %d",
		 conn.from_element()->name_c_str(), type1, conn.from_port(),
		 conn.to_element()->name_c_str(), type2, conn.to_port());
}

void
ProcessingT::check_processing(ErrorHandler *errh)
{
    // add fake connections for agnostics
    Vector<ConnectionT> conn = _router->connections();
    Bitvector bv;
    for (int i = 0; i < ninput_pidx(); i++)
	if (_input_processing[i] == VAGNOSTIC) {
	    ElementT *e = const_cast<ElementT *>(_input_elt[i]);
	    int ei = e->eindex();
	    int port = i - _input_pidx[ei];
	    int opidx = _output_pidx[ei];
	    int noutputs = _output_pidx[ei+1] - opidx;
	    forward_flow(e->type()->traits().flow_code,
			 port, noutputs, &bv, errh);
	    for (int j = 0; j < noutputs; j++)
		if (bv[j] && _output_processing[opidx + j] == VAGNOSTIC)
		    conn.push_back(ConnectionT(PortT(e, j), PortT(e, port), "<agnostic>"));
	}

    // spread personalities
    while (true) {
    
	bool changed = false;
	for (int c = 0; c < conn.size(); c++) {
	    if (conn[c].dead())
		continue;

	    int offf = output_pidx(conn[c].from());
	    int offt = input_pidx(conn[c].to());
	    int pf = _output_processing[offf];
	    int pt = _input_processing[offt];

	    switch (pt) {
	
	      case VAGNOSTIC:
		if (pf != VAGNOSTIC) {
		    _input_processing[offt] = pf;
		    changed = true;
		}
		break;
	
	      case VPUSH:
	      case VPULL:
		if (pf == VAGNOSTIC) {
		    _output_processing[offf] = pt;
		    changed = true;
		} else if (pf != pt) {
		    processing_error(conn[c], pf, errh);
		    conn[c].kill();
		}
		break;
	
	    }
	}

	if (!changed)
	    break;
    }
}

static const char *
processing_name(int p)
{
  if (p == ProcessingT::VAGNOSTIC)
    return "agnostic";
  else if (p == ProcessingT::VPUSH)
    return "push";
  else if (p == ProcessingT::VPULL)
    return "pull";
  else
    return "?";
}

void
ProcessingT::check_connections(ErrorHandler *errh)
{
    Vector<int> input_used(ninput_pidx(), -1);
    Vector<int> output_used(noutput_pidx(), -1);

    // Check each hookup to ensure it doesn't reuse a port
    const Vector<ConnectionT> &conn = _router->connections();
    for (int c = 0; c < conn.size(); c++) {
	if (conn[c].dead())
	    continue;

	const PortT &hf = conn[c].from(), &ht = conn[c].to();
	int fp = output_pidx(hf), tp = input_pidx(ht);

	if (_output_processing[fp] == VPUSH && output_used[fp] >= 0) {
	    errh->lerror(conn[c].landmark(),
			 "reuse of '%s' push output %d",
			 hf.element->name_c_str(), hf.port);
	    errh->lmessage(conn[output_used[fp]].landmark(),
			   "  '%s' output %d previously used here",
			   hf.element->name_c_str(), hf.port);
	} else
	    output_used[fp] = c;

	if (_input_processing[tp] == VPULL && input_used[tp] >= 0) {
	    errh->lerror(conn[c].landmark(),
			 "reuse of '%s' pull input %d",
			 ht.element->name_c_str(), ht.port);
	    errh->lmessage(conn[input_used[tp]].landmark(),
			   "  '%s' input %d previously used here",
			   ht.element->name_c_str(), ht.port);
	} else
	    input_used[tp] = c;
    }

    // Check for unused inputs and outputs, set _connected_* properly.
    for (int i = 0; i < ninput_pidx(); i++)
	if (input_used[i] < 0) {
	    const ElementT *e = _input_elt[i];
	    if (e->dead())
		continue;
	    int port = i - _input_pidx[e->eindex()];
	    errh->lerror(e->landmark(),
			 "'%s' %s input %d not connected",
			 e->name_c_str(), processing_name(_input_processing[i]), port);
	}

    for (int i = 0; i < noutput_pidx(); i++)
	if (output_used[i] < 0) {
	    const ElementT *e = _output_elt[i];
	    if (e->dead())
		continue;
	    int port = i - _output_pidx[e->eindex()];
	    errh->lerror(e->landmark(),
			 "'%s' %s output %d not connected",
			 e->name_c_str(), processing_name(_output_processing[i]), port);
	}

    // Set _connected_* properly.
    PortT crap(0, -1);
    _connected_input.assign(ninput_pidx(), crap);
    _connected_output.assign(noutput_pidx(), crap);
    for (int i = 0; i < ninput_pidx(); i++)
	if (_input_processing[i] == VPULL && input_used[i] >= 0)
	    _connected_input[i] = conn[ input_used[i] ].from();
    for (int i = 0; i < noutput_pidx(); i++)
	if (_output_processing[i] == VPUSH && output_used[i] >= 0)
	    _connected_output[i] = conn[ output_used[i] ].to();
}

int
ProcessingT::reset(const RouterT *r, ElementMap *emap, bool flatten,
		   ErrorHandler *errh)
{
    _router = r;
    if (!errh)
	errh = ErrorHandler::silent_handler();
    int before = errh->nerrors();

    ElementMap::push_default(emap);

    // create pidx and elt arrays, warn about dead elements
    create_pidx(errh);
    
    initial_processing(errh);
    check_processing(errh);

    // 'flat' configurations have no agnostic ports; change them to push
    if (flatten)
	resolve_agnostics();
    
    check_connections(errh);

    ElementMap::pop_default();

    if (errh->nerrors() != before)
	return -1;
    return 0;
}

void
ProcessingT::resolve_agnostics()
{
    for (int i = 0; i < _input_processing.size(); i++)
	if (_input_processing[i] == VAGNOSTIC)
	    _input_processing[i] = VPUSH;
    for (int i = 0; i < _output_processing.size(); i++)
	if (_output_processing[i] == VAGNOSTIC)
	    _output_processing[i] = VPUSH;