processingt.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 -*-
/*
 * 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
 * Copyright (c) 2007 Regents of the University of California
 * Copyright (c) 2008-2009 Meraki, Inc.
 *
 * 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 <click/confparse.hh>
#include "elementmap.hh"
#include <string.h>
#include <algorithm>

const char ProcessingT::processing_letters[] = "ahlXahlX";
const char ProcessingT::decorated_processing_letters[] = "ahlXaHLX";

static String dpcode_push("h");
static String dpcode_pull("l");
static String dpcode_agnostic("a");
static String dpcode_apush("H");
static String dpcode_apull("L");
static String dpcode_push_to_pull("h/l");

ProcessingT::ProcessingT(bool resolve_agnostics, RouterT *router,
			 ElementMap *emap, ErrorHandler *errh)
    : _router(router), _element_map(emap), _scope(router->scope())
{
    create("", resolve_agnostics, errh);
}

ProcessingT::ProcessingT(RouterT *router, ElementMap *emap, ErrorHandler *errh)
    : _router(router), _element_map(emap), _scope(router->scope())
{
    create("", true, errh);
}

ProcessingT::ProcessingT(const ProcessingT &processing, ElementT *element,
			 ErrorHandler *errh)
    : _element_map(processing._element_map), _scope(processing._scope)
{
    assert(element->router() == processing._router);
    ElementClassT *t = element->resolve(processing._scope, &_scope, errh);
    _router = t->cast_router();
    assert(_router);
    if (!processing._router_name)
	_router_name = element->name();
    else
	_router_name = processing._router_name + "/" + element->name();

    String prefix = _router_name + "/";
    for (HashTable<String, String>::const_iterator it = processing._flow_overrides.begin();
	 it != processing._flow_overrides.end(); ++it)
	if (it.key().starts_with(prefix))
	    _flow_overrides.set(it.key().substring(prefix.length()), it.value());

    create(processing.processing_code(element), true, errh);
}

void
ProcessingT::check_types(ErrorHandler *errh)
{
    Vector<ElementClassT *> types;
    _router->collect_locally_declared_types(types);
    for (Vector<ElementClassT *>::iterator ti = types.begin(); ti != types.end(); ++ti)
	if (RouterT *rx = (*ti)->cast_router()) {
	    ProcessingT subp(rx, _element_map, errh);
	    subp.check_types(errh);
	}
}

void
ProcessingT::create(const String &compound_pcode, bool resolve_agnostics,
		    ErrorHandler *errh)
{
    LocalErrorHandler lerrh(errh);
    ElementMap::push_default(_element_map);

    // create pidx and elt arrays, warn about dead elements
    create_pidx(&lerrh);
    initial_processing(compound_pcode, &lerrh);
    check_processing(&lerrh);
    // change remaining agnostic ports to agnostic-push
    if (resolve_agnostics)
	this->resolve_agnostics();
    check_connections(&lerrh);

    ElementMap::pop_default();
}

void
ProcessingT::parse_flow_info(ElementT *e, ErrorHandler *)
{
    Vector<String> conf;
    cp_argvec(cp_expand(e->configuration(), _scope), conf);
    for (String *it = conf.begin(); it != conf.end(); ++it) {
	String name = cp_shift_spacevec(*it);
	String value = cp_shift_spacevec(*it);
	if (name && value && !*it)
	    _flow_overrides.set(name, value);
    }
}

void
ProcessingT::create_pidx(ErrorHandler *errh)
{
    int ne = _router->nelements();
    _pidx[end_to].assign(ne, 0);
    _pidx[end_from].assign(ne, 0);
    ElementClassT *flow_info = ElementClassT::base_type("FlowInfo");

    // count used input and output ports for each element
    int ci = 0, co = 0;
    for (int i = 0; i < ne; i++) {
	_pidx[end_to][i] = ci;
	_pidx[end_from][i] = co;
	ElementT *e = _router->element(i);
	ci += e->ninputs();
	co += e->noutputs();
	if (e->resolved_type(_scope) == flow_info)
	    parse_flow_info(e, errh);
    }
    _pidx[end_to].push_back(ci);
    _pidx[end_from].push_back(co);

    // create eidxes
    _elt[end_to].clear();
    _elt[end_from].clear();
    ci = 0, co = 0;
    for (int i = 1; i <= ne; i++) {
	const ElementT *e = _router->element(i - 1);
	for (; ci < _pidx[end_to][i]; ci++)
	    _elt[end_to].push_back(e);
	for (; co < _pidx[end_from][i]; co++)
	    _elt[end_from].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->decorated_landmark(), "dead element %s has live connections", x->name_c_str());
    }
}

const char *
ProcessingT::processing_code_next(const char *code, const char *end_code, int &processing)
{
    assert(code <= end_code);
    if (code == end_code) {
	processing = -1;
	return code;
    } else if (*code == 'h')
	processing = ppush;
    else if (*code == 'l')
	processing = ppull;
    else if (*code == 'a')
	processing = pagnostic;
    else if (*code == 'H')
	processing = ppush + pagnostic;
    else if (*code == 'L')
	processing = ppull + pagnostic;
    else {
	processing = -1;
	return code;
    }
    const char *nc = code + 1;
    if (nc != end_code && *nc == '@') {
	processing += perror;
	++nc;
    }
    if (nc == end_code || *nc == '/')
	return code;
    else
	return nc;
}

String
ProcessingT::processing_code_reverse(const String &s)
{
    const char *slash = find(s.begin(), s.end(), '/');
    if (slash != s.end())
	return s.substring(slash + 1, s.end()) + "/" + s.substring(s.begin(), slash);
    else
	return s;
}

void
ProcessingT::initial_processing_for(int ei, const String &compound_pcode, ErrorHandler *errh)
{
    // don't handle uprefs or tunnels
    const ElementT *e = _router->element(ei);
    // resolved_type() errors reported in check_nports(), do not pass errh here
    ElementClassT *etype = e->resolved_type(_scope);
    if (!etype)
	return;

    // fetch initial processing code
    String pc;
    if (e->tunnel() && (e->name() == "input" || e->name() == "output"))
	pc = compound_pcode;
    else
	pc = etype->traits().processing_code;
    if (!pc) {
	int &class_warning = _class_warnings[etype];
	if (!e->tunnel() && !(class_warning & classwarn_unknown)) {
	    class_warning |= classwarn_unknown;
	    errh->lwarning(e->decorated_landmark(), "unknown element class %<%s%>", etype->printable_name_c_str());
	}
	return;
    }

    // parse processing code
    const char *pcpos = pc.begin();

    int start_in = _pidx[end_to][ei];
    int start_out = _pidx[end_from][ei];

    int val;
    for (int i = 0; i < e->ninputs(); i++) {
	pcpos = processing_code_next(pcpos, pc.end(), val);
	if (val < 0) {
	    int &cwarn = _class_warnings[etype];
	    if (!(cwarn & classwarn_pcode)) {
		// "String(pc).c_str()" so pcpos remains valid
		errh->lerror(e->landmark(), "syntax error in processing code %<%s%> for %<%s%>", String(pc).c_str(), etype->printable_name_c_str());
		cwarn |= classwarn_pcode;
	    }
	    val = pagnostic;
	}
	_processing[end_to][start_in + i] = (val & pagnostic ? pagnostic : val);
    }

    pcpos = processing_code_output(pc.begin(), pc.end(), pcpos);

    for (int i = 0; i < e->noutputs(); i++) {
	pcpos = processing_code_next(pcpos, pc.end(), val);
	if (val < 0) {
	    int &cwarn = _class_warnings[etype];
	    if (!(cwarn & classwarn_pcode)) {
		// "String(pc).c_str()" so pcpos remains valid
		errh->lerror(e->landmark(), "syntax error in processing code %<%s%> for %<%s%>", String(pc).c_str(), etype->printable_name_c_str());
		cwarn |= classwarn_pcode;
	    }
	    val = pagnostic;
	}
	_processing[end_from][start_out + i] = (val & pagnostic ? pagnostic : val);
    }
}

void
ProcessingT::initial_processing(const String &compound_pcode, ErrorHandler *errh)
{
    _processing[end_to].assign(ninput_pidx(), pagnostic);
    _processing[end_from].assign(noutput_pidx(), pagnostic);
    String reversed_pcode = processing_code_reverse(compound_pcode);
    for (int i = 0; i < nelements(); i++)
	initial_processing_for(i, reversed_pcode, errh);
}

void
ProcessingT::processing_error(const ConnectionT &conn, int processing_from,
			      ErrorHandler *errh)
{
  const char *type1 = (processing_from & ppush ? "push" : "pull");
  const char *type2 = (processing_from & ppush ? "pull" : "push");
  if (conn.landmark() == "<agnostic>")
    errh->lerror(conn.from_element()->decorated_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.decorated_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());
  _processing[end_to][input_pidx(conn)] |= perror;
  _processing[end_from][output_pidx(conn)] |= perror;
}

void
ProcessingT::check_processing(ErrorHandler *errh)
{
    // add fake connections for agnostics
    LandmarkT agnostic_landmark("<agnostic>");
    Vector<ConnectionT> conn = _router->connections();
    Bitvector bv;
    for (int i = 0; i < ninput_pidx(); i++)
	if (_processing[end_to][i] == pagnostic) {
	    ElementT *e = const_cast<ElementT *>(_elt[end_to][i]);
	    int ei = e->eindex();
	    int port = i - _pidx[end_to][ei];
	    int opidx = _pidx[end_from][ei];
	    int noutputs = _pidx[end_from][ei+1] - opidx;
	    forward_flow(flow_code(e), port, &bv, noutputs, errh);
	    for (int j = 0; j < noutputs; j++)
		if (bv[j] && _processing[end_from][opidx + j] == pagnostic)
		    conn.push_back(ConnectionT(PortT(e, j), PortT(e, port), agnostic_landmark));
	}

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

	    int offf = output_pidx(conn[c].from());
	    int offt = input_pidx(conn[c].to());
	    int pf = _processing[end_from][offf];
	    int pt = _processing[end_to][offt];

	    switch (pt & 7) {

	      case pagnostic:
		if (pf != pagnostic) {
		    _processing[end_to][offt] = pagnostic | (pf & 3);
		    changed = true;
		}
		break;

	      case ppush:
	      case ppull:
	      case ppush + pagnostic:
	      case ppull + pagnostic:
		if (pf == pagnostic) {
		    _processing[end_from][offf] = pagnostic | (pt & 3);
		    changed = true;
		} else if (((pf ^ pt) & 3) != 0) {
		    processing_error(conn[c], pf, errh);
		    conn[c] = ConnectionT();
		}
		break;

	      default:
		assert(0);

	    }
	}

	if (!changed)
	    break;
    }
}

static const char *
processing_name(int p)
{
    p &= 7;
    if (p == ProcessingT::pagnostic)
	return "agnostic";
    else if (p & ProcessingT::ppush)
	return "push";
    else if (p & ProcessingT::ppull)
	return "pull";
    else
	return "?";
}

static int
notify_nports_pair(const char *&s, const char *ends, int &lo, int &hi)
{
    if (s == ends || *s == '-')
	lo = 0;
    else if (isdigit((unsigned char) *s))
	s = cp_integer(s, ends, 10, &lo);
    else
	return -1;
    if (s < ends && *s == '-') {
	s++;
	if (s < ends && isdigit((unsigned char) *s))
	    s = cp_integer(s, ends, 10, &hi);
	else
	    hi = INT_MAX;
    } else
	hi = lo;
    return 0;
}

void
ProcessingT::check_nports(const ElementT *e, const int *input_used, const int *output_used, ErrorHandler *errh)
{
    String port_count = e->resolved_type(_scope, errh)->port_count_code();
    const char *s_in = port_count.c_str();
    const char *s = s_in, *ends = s + port_count.length();
    int ninputs, ninlo, ninhi, noutlo, nouthi, equal = 0;
    StringAccum equalmsg;

    if (s == ends)		// no information about element; assume OK
	return;

    if (notify_nports_pair(s, ends, ninlo, ninhi) < 0)
	goto parse_error;

    if (s == ends)
	s = s_in;
    else if (*s == '/')
	s++;
    else
	goto parse_error;

    if (*s == '=') {
	const char *plus = s + 1;
	do {
	    equal++;
	} while (plus != ends && *plus++ == '+');
	if (plus != ends)
	    equal = 0;
    }
    if (!equal)
	if (notify_nports_pair(s, ends, noutlo, nouthi) < 0 || s != ends)
	    goto parse_error;

    ninputs = e->ninputs();
    if (ninputs < ninlo) {
	errh->lerror(e->decorated_landmark(), "too few inputs for %<%s%>, %s%d required", e->name_c_str(), (ninlo == ninhi ? "" : "at least "), ninlo);
	ninputs = ninlo;
    } else if (ninputs > ninhi) {
	const Vector<ConnectionT> &conn = _router->connections();
	errh->lerror(e->decorated_landmark(), "too many inputs for %<%s%>, %s%d allowed", e->name_c_str(), (ninlo == ninhi ? "" : "at most "), ninhi);
	for (int i = ninhi; i < e->ninputs(); i++)
	    if (input_used[i] >= 0)
		errh->lmessage(conn[input_used[i]].decorated_landmark(),
			       "  %<%s%> input %d used here", e->name_c_str(), i);
	ninputs = ninhi;
    }

    if (equal) {
	noutlo = nouthi = ninputs + equal - 1;
	if (e->noutputs() != noutlo)
	    equalmsg << " with " << ninputs << " input" << (ninputs == 1 ? "" : "s");
    }
    if (e->noutputs() < noutlo)
	errh->lerror(e->decorated_landmark(), "too few outputs for %<%s%>%s, %s%d required", e->name_c_str(), equalmsg.c_str(), (noutlo == nouthi ? "" : "at least "), noutlo);
    else if (e->noutputs() > nouthi) {
	const Vector<ConnectionT> &conn = _router->connections();
	errh->lerror(e->decorated_landmark(), "too many outputs for %<%s%>%s, %s%d allowed", e->name_c_str(), equalmsg.c_str(), (noutlo == nouthi ? "" : "at most "), nouthi);
	for (int i = nouthi; i < e->noutputs(); i++)
	    if (output_used[i] >= 0)
		errh->lmessage(conn[output_used[i]].decorated_landmark(),
			       "  %<%s%> output %d used here", e->name_c_str(), i);
    }

    return;

  parse_error:
    errh->lerror(e->decorated_landmark(), "syntax error in port count code for %<%s%>", e->type()->printable_name_c_str());
}

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())