Logo Search packages:      
Sourcecode: tcng version File versions  Download package

if_ext.c

/*
 * if_ext.c - Processing of the "if" command, using external matcher
 *
 * Written 2001-2003 by Werner Almesberger 
 * Copyright 2001 Network Robots
 * Copyright 2002 Bivio Networks, Network Robots, Werner Almesberger
 * Copyright 2003 Werner Almesberger
 */

/*
 * Description of invocation and data format in ../doc/external.tex
 *
 * NOTE: if_ext.c does not yet implement the functionality described in
 *       external.tex !
 */

/*
 * @@@ KNOWN BUG: we may generate actions that are never used, because the
 * corresponding rule is eliminated.
 */


#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <assert.h>
#include <time.h>
#include <sys/wait.h>

#include "config.h"
#include "util.h"
#include "error.h"
#include "tree.h"
#include "data.h"
#include "field.h"
#include "op.h"
#include "tc.h"
#include "iflib.h"
#include "if.h"
#include "ext.h"


int generate_default_class; /* if_ext generates default classes */
int use_bit_tree; /* use experimental bit tree algorithm */
int no_combine; /* don't combine ifs into single expression */


/* ----------------------------- Offset groups ----------------------------- */


static struct offset_group {
    int number;         /* offset group number */
    int base;           /* offset group this group adds to */
    int value_base;     /* offset group of the access */
    int offset;         /* constant offset of access */
    int length;         /* length of access */
    int shift;          /* left-shift by that many bits */
    struct offset_group *next;
} *offset_groups = NULL;


static int next_offset_group = AUTO_OFFSET_GROUP_BASE;


static int lookup_offset_group(int base,int value_base,int offset,int length,
  int shift)
{
    struct offset_group **walk;

    if (debug > 1)
      debugf("lookup_offset_group(base %d,%d:%d:%d)",base,value_base,offset,
        length);
    for (walk = &offset_groups; *walk; walk = &(*walk)->next)
      if ((*walk)->base == base && (*walk)->value_base == value_base &&
        (*walk)->offset == offset && (*walk)->length == length &&
        (*walk)->shift == shift) {
          if (debug > 1)
            debugf("lookup_offset_group: found %d",(*walk)->number);
          return (*walk)->number;
      }
    while (offset_group_taken(next_offset_group)) next_offset_group++;
    *walk = alloc_t(struct offset_group);
    (*walk)->number = next_offset_group++;
    (*walk)->base = base;
    (*walk)->value_base = value_base;
    (*walk)->offset = offset;
    (*walk)->length = length;
    (*walk)->shift = shift;
    (*walk)->next = NULL;
    if (debug > 1) debugf("lookup_offset_group: new %d",(*walk)->number);
    return (*walk)->number;
}


static int build_offset_group(int base,int value_base,DATA d);


/*
 * @@@ Merge this with iflib_red.c:do_optimize_eq
 */

static int new_offset_group(int base,int value_base,DATA d)
{
    uint32_t mask = 0xffffffff;
    int shift = 3; /* we're bit-based, op_offset is byte-based */
    int offset,length;

    if (debug > 1)
      debugf("new_offset_group(base %d,value_base %d)",base,value_base);
    while (d.op && d.op->dsc != &op_access) {
      if (d.op->dsc == &op_shift_left) {
          if (d.op->b.op || d.op->b.type != dt_unum)
            dump_failed(d,"bad left shift");
          shift += d.op->b.u.unum;
          mask >>= d.op->b.u.unum;
          d = d.op->a;
          continue;
      }
      if (d.op->dsc == &op_shift_right) {
          if (d.op->b.op || d.op->b.type != dt_unum)
            dump_failed(d,"bad right shift");
          shift -= d.op->b.u.unum;
          mask <<= d.op->b.u.unum;
          d = d.op->a;
          continue;
      }
      if (d.op->dsc == &op_and) {
           if (!d.op->a.op && d.op->a.type == dt_unum) {
            mask &= d.op->a.u.unum;
            d = d.op->b;
          }
          else {
            if (d.op->b.op || d.op->b.type != dt_unum)
                dump_failed(d,"no constant in and");
            mask &= d.op->b.u.unum;
            d = d.op->a;
            }
          continue;
        }
      if (d.op->dsc == &op_field_root) {
          value_base = d.op->b.u.field_root->offset_group;
          d = d.op->a;
          continue;
      }
      if (d.op->dsc == &op_offset) {
          value_base = build_offset_group(value_base,value_base,d.op->b);
          d = d.op->a;
          continue;
      }
        dump_failed(d,"bad operator");
    }
    assert(d.op && d.op->dsc == &op_access);
    assert(!d.op->b.op && d.op->b.type == dt_unum);
    assert(!d.op->c.op && d.op->c.type == dt_unum);
    offset = d.op->b.u.unum*8;
    length = d.op->c.u.unum;
    assert(length);
    if (!mask) return base;
    while (!(mask & 1)) {
      length--;
      mask >>= 1;
      shift++;
    }
    if (shift < 0) dump_failed(d,"negative shift");
    mask <<= 32-length;
    if (!mask) return base;
    while (!(mask & 0x80000000)) {
      offset++;
      length--;
      mask <<= 1;
    }
    return lookup_offset_group(base,value_base,offset,length,shift);
}


static int build_offset_group(int base,int value_base,DATA d)
{
    if (debug > 1)
      debugf("build_offset_group(base %d,value_base %d)",base,value_base);
    while (d.op && d.op->dsc == &op_plus) {
      base = build_offset_group(base,value_base,d.op->a);
      d = d.op->b;
    }
    return new_offset_group(base,value_base,d);
}


int get_offset_group(DATA d,int base); /* shared with iflib_bit.c */
int get_offset_group(DATA d,int base)
{
    assert(d.op && d.op->dsc == &op_offset);
    if (debug > 1) debugf("get_offset_group(base %d)",base);
    return build_offset_group(base,base,d.op->b);
}


static void do_scan_offsets(DATA d,int base)
{
    if (debug > 1) debugf("scan_offsets(base %d)",base);
    if (!d.op) return;
    if (d.op->dsc == &op_field_root) base = d.op->b.u.field_root->offset_group;
    if (d.op->dsc == &op_offset) base = get_offset_group(d,base);
    do_scan_offsets(d.op->a,base);
    do_scan_offsets(d.op->b,base);
    do_scan_offsets(d.op->c,base);
}


static void scan_offsets(DATA d)
{
    do_scan_offsets(d,0);
}


static void dump_offsets(FILE *file)
{
    struct offset_group *group;

    for (group = offset_groups; group; group = group->next)
      fprintf(file,"offset %d = %d+(%d:%d:%d << %d)\n",group->number,
        group->base,group->value_base,group->offset,group->length,
        group->shift);
}


void reset_offsets(void)
{
    while (offset_groups) {
      struct offset_group *next = offset_groups->next;

      free(offset_groups);
      offset_groups = next;
    }
    next_offset_group = AUTO_OFFSET_GROUP_BASE;
}


/* ----------------------------- Actions group ----------------------------- */


static void dump_actions(DATA d)
{
    if (debug > 1) debugf("dump_actions");
    if (action_tree(d)) {
      register_actions(d);
      return;
    }
    if (!d.op) return;
    dump_actions(d.op->a);
    dump_actions(d.op->b);
    dump_actions(d.op->c);
}


/* -------------------------------- Matches -------------------------------- */


/*
 * This isn't exactly optimized for speed ...
 */


static struct bit_match {
    int offset_group;
    int offset;
    int value;
    struct bit_match *next;
} *bits = NULL,**next_bit = &bits;


static void sort_bits(void)
{
    struct bit_match *i,*j,tmp;

    /* ye ole bubblesort */
    /* sort within offset_group by offset (@@@ don't sort by offset_group for
       now - need to walk groups to extract partial order) */
    for (i = bits; i; i = i->next)
      for (j = i->next; j; j = j->next)
          if (i->offset_group == j->offset_group && i->offset > j->offset) {
            struct bit_match *i_next = i->next,*j_next = j->next;

            tmp = *i;
            *i = *j;
            *j = tmp;
            i->next = i_next;
            j->next = j_next;
          }
    /* TODO: check if this is really valid wrt ordering constraints @@@ */
}


static void collect_bits(FILE *file)
{
    struct bit_match *walk,*end;

    for (walk = bits; walk; walk = end) {
      struct bit_match *scan;
      int length = 1;
      int next_offset = walk->offset;
      int nibble = 0;

      for (end = walk->next; end && walk->offset_group == end->offset_group
        && end->offset == ++next_offset; end = end->next)
          length++;
      fprintf(file," %d:%d:%d=0x",walk->offset_group,walk->offset,length);
      for (scan = walk; length; scan = scan->next) {
          length--;
          nibble |= scan->value << (length & 3);
          if (!(length & 3)) {
            fputc(nibble >= 10 ? nibble+'A'-10 : nibble+'0',file);
            nibble = 0;
          }
      }
    }
}


static void drop_bits(void)
{
    struct bit_match *next;

    while (bits) {
      next = bits->next;
      free(bits);
      bits = next;
    }
    next_bit = &bits;
}


/*
 * bit_match returns 1 if the bit was added (or if it redundant), 0 if the test
 * would cause a conflict, so we should discard the rule.
 */


static int bit_match(int offset_group,int offset,int value)
{
    struct bit_match *bit;

    for (bit = bits; bit; bit = bit->next)
      if (bit->offset_group == offset_group && bit->offset == offset)
          return bit->value == value; /* bit is redundant or conflicting */
    bit = alloc_t(struct bit_match);
    bit->offset_group = offset_group;
    bit->offset = offset;
    bit->value = value;
    bit->next = NULL;
    *next_bit = bit;
    next_bit = &bit->next;
    return 1;
}


/*
 * Returns 0 if the rule always fails.
 */


static int do_decompose_match(int offset_group,int offset,U128 mask128,
  U128 value128)
{
    int i;

    for (i = 3; i >= 0; i--) {
      uint32_t mask = mask128.v[i],value = value128.v[i];
      int off;

      debugf2("| [%d] mask 0x%lx, value 0x%lx",i,(unsigned long) mask,
        (unsigned long) value);
      for (off = offset+(3-i)*32; mask; off++) {
          if (mask & 0x80000000)
            if (!bit_match(offset_group,off,value >> 31)) return 0;
          mask <<= 1;
          value <<= 1;
      }
    }
    return 1;
}


static int decompose_match(int offset_group,int offset,int length,
  U128 mask,U128 value)
{
    debugf("decompose_match(off_grp %d,offset %d, length %d)",offset_group,
      offset,length);
    /* if (value & ~mask) return 0; */
    if (!u128_is_zero(u128_and(value,u128_not(mask)))) return 0;
    return do_decompose_match(offset_group,offset,
      u128_shift_left(mask,128-length),u128_shift_left(value,128-length));
}


static int dump_match(DATA d,int offset_group)
{
    DATA a,b;
    int bits;
    U128 mask = u128_not(u128_from_32(0));

    assert(d.op && d.op->dsc == &op_eq);
    /* @@@ policing */
    a = d.op->a;
    b = d.op->b;
    if (!a.op) {
      if (!b.op) dump_failed(d,"constant expression");
      a = b;
      b = d.op->a;
    }
    if (b.type != dt_unum && b.type != dt_ipv6) dump_failed(d,"eq non-number");
    while (a.op && a.op->dsc != &op_access) {
      if (a.op->dsc == &op_and) {
          /* iflib_arith normalizes  const & access  to  access & const  */
          if (a.op->b.op ||
            (a.op->b.type != dt_unum && a.op->b.type != dt_ipv6))
            dump_failed(d,"must be \"& constant\"");
          mask = u128_and(mask,data_convert(a.op->b,dt_ipv6).u.u128);
          a = a.op->a;
          continue;
      }
      if (a.op->dsc == &op_field_root) {
          offset_group = a.op->b.u.field_root->offset_group;
          a = a.op->a;
          continue;
      }
      if (a.op->dsc == &op_offset) {
          offset_group = get_offset_group(a,offset_group);
          a = a.op->a;
          continue;
      }
      dump_failed(d,"bad operator");
    }
    if (!a.op || a.op->dsc != &op_access)
      dump_failed(d,"access expected");
    bits = a.op->c.u.unum;
    assert(bits);
    /*
     * No longer needed - iflib_arith does this for us now
    mask &= (((1 << (bits-1))-1) << 1) | 1; / * (1 << bits)-1 * /
     */
    return decompose_match(offset_group,a.op->b.u.unum*8,bits,mask,
      data_convert(b,dt_ipv6).u.u128);
}


/* ------------------------------ Rules group ------------------------------ */


static void dump_action(FILE *file,const DATA *d)
{
    fprintf(file,"match");
    sort_bits();
    collect_bits(file);
    drop_bits();
    fprintf(file," action %d\n",action_number(*d));
}


static int dump_or(FILE *file,const DATA *d,int offset_group);


static int dump_other(FILE *file,const DATA *d,int offset_group)
{
    if (debug > 1) debugf("dump_other(offset_group %d)",offset_group);
    if (d->op && d->op->dsc == &op_eq) return dump_match(*d,offset_group);
    if (action_tree(*d)) {
      dump_action(file,d);
      return 1;
    }
    if (d->op && d->op->dsc == &op_field_root)
      return dump_or(file,&d->op->a,d->op->b.u.field_root->offset_group);
    if (d->op && d->op->dsc == &op_offset)
      return dump_or(file,&d->op->a,get_offset_group(*d,offset_group));
    dump_failed(*d,"bad operator");
    return 0; /* not reached */
}


static int dump_and(FILE *file,const DATA *d,int offset_group)
{
    if (debug > 1) debugf("dump_and(offset_group %d)",offset_group);
    while (d->op && d->op->dsc == &op_logical_and && !action_tree(*d)) {
      if (!dump_other(file,&d->op->a,offset_group)) {
          drop_bits();
          return 0;
      }
      d = &d->op->b;
    }
    return dump_other(file,d,offset_group);
}


static int dump_or(FILE *file,const DATA *d,int offset_group)
{
    int useful = 1;

    if (debug > 1) debugf("dump_or(offset_group %d)",offset_group);
    while (d->op && d->op->dsc == &op_logical_or && !action_tree(*d)) {
      if (dump_and(file,&d->op->a,offset_group)) useful = 1;
      d = &d->op->b;
    }
    return dump_and(file,d,offset_group) || useful;
}


static void dump_rules(FILE *file,const DATA *d)
{
    if (debug) printf("--- dump_rules ---\n");
    (void) dump_or(file,d,0);
}


/* ----------------------------- Global pragma ----------------------------- */


void dump_pragma(FILE *file)
{
    const DATA_LIST *walk;

    if (!pragma) return;
    fprintf(file,"pragma");
    for (walk = pragma; walk; walk = walk->next)
      fprintf(file," %s",walk->ref->u.string);
    fputc('\n',file);
}


/* ----------------------------- Queues group ------------------------------ */


void dump_block(FILE *file,const QDISC *q)
{
    const DEVICE *dev = q->parent.device;

    fprintf(file,"block %s %s",dev->name,dev->ingress == q ? "ingress" :
      "egress");
    if (prm_present(dev->params,&prm_pragma)) {
      const DATA_LIST *pragma;

      for (pragma = prm_data(dev->params,&prm_pragma).u.list;
        pragma; pragma = pragma->next)
          fprintf(file," %s",pragma->ref->u.string);
    }
    fputc('\n',file);
}


/* ----------------------------- Buckets group ----------------------------- */


static struct bucket {
    const POLICE *p;
    struct bucket *next;
} *buckets = NULL;


static void add_bucket(const POLICE *p)
{
    struct bucket **last;

    param_get(p->params,p->location);
    if (!prm_rate.present && prm_peakrate.present)
      error("if_ext only supports single-rate token bucket policer");
    for (last = &buckets; *last; last = &(*last)->next)
      if ((*last)->p == p) return;
    *last = alloc_t(struct bucket);
    (*last)->p = p;
    (*last)->next = NULL;
}


static void collect_buckets(const DATA *d)
{
    if (!d->op && (d->type == dt_police || d->type == dt_bucket)) { /* @@@ */
      const POLICE *p = d->u.police;

      param_get(p->params,p->location);
      if (prm_present(p->params,&prm_overflow))
          add_bucket(prm_data(p->params,&prm_overflow).u.police);
      add_bucket(d->u.police);
      return;
    }
    if (d->op) {
      collect_buckets(&d->op->a);
      collect_buckets(&d->op->b);
      collect_buckets(&d->op->c);
    }
}


static void dump_buckets(FILE *file)
{
    struct bucket *bucket;

    for (bucket = buckets; bucket; bucket = bucket->next) {
      int overflow = 0;

      param_get(bucket->p->params,bucket->p->location);
      if (prm_present(bucket->p->params,&prm_overflow))
          overflow =
            prm_data(bucket->p->params,&prm_overflow).u.police->number;
      fprintf(file,"bucket %d = %lu %lu %lu %lu %d",
        (int) bucket->p->number,(unsigned long) prm_rate.v,
        prm_mpu.present ? (unsigned long) prm_mpu.v : 0,
        (unsigned long) prm_burst.v,(unsigned long) prm_burst.v,
        overflow);
      if (prm_present(bucket->p->params,&prm_pragma)) {
          const DATA_LIST *pragma;

          for (pragma = prm_data(bucket->p->params,&prm_pragma).u.list;
            pragma; pragma = pragma->next)
            fprintf(file," %s",pragma->ref->u.string);
      }
      fputc('\n',file);
    }
    while (buckets) {
      struct bucket *next;

      next = buckets->next;
      free(buckets);
      buckets = next;
    }
}


/* ------------------------------------------------------------------------- */


static void dump_if_ext_expr(const FILTER *filter,DATA *d)
{
    /*
     * Normalize again, possibly undoing previous optimizations.
     * External program will do its own expression optimization.
     */
    iflib_arith(d);
    iflib_not(d);
    if (!use_bit_tree) {
      iflib_reduce(d);
      iflib_normalize(d);
      iflib_actions(filter->location,d);
    }
    iflib_offset(d,0); /* don't combine */
    debug_expr("BEFORE dumping",*d);
    scan_offsets(*d);
    collect_buckets(d);
}


static void dump_if_ext_prep_callback(const ELEMENT *e,void *user)
{
    DATA *d = prm_data_ptr(e->params,&prm_if_expr);

    complement_decisions(d,e->parent.class);
    *d = op_binary(&op_logical_or,*d,data_decision(dr_continue,NULL));
    dump_if_ext_expr(e->parent.filter,d);
}


void dump_if_ext_prepare(const FILTER *filter)
{
    QDISC *qdisc = filter->parent.qdisc;

    if (prm_present(filter->params,&prm_pragma))
      lwarn(filter->location,
        "\"pragma\" on \"if\" ignored by external target");
    if (!no_combine) {
      DATA *d = &qdisc->if_expr;

      qdisc->if_expr = iflib_combine(qdisc);
      if (!generate_default_class)
          *d = op_binary(&op_logical_or,*d,data_decision(dr_continue,NULL));
      else {
          if (!qdisc->dsc->default_class)
            lerrorf(qdisc->location,
              "qdisc \"%s\" does not provide default class",
              qdisc->dsc->name);
          qdisc->dsc->default_class(d,qdisc);
      }
      dump_if_ext_expr(filter,d);
    }
    else {
      iflib_comb_iterate(qdisc,dump_if_ext_prep_callback,NULL);
      if (generate_default_class) {
          DATA tmp;

          if (!qdisc->dsc->default_class)
            lerrorf(qdisc->location,
              "qdisc \"%s\" does not provide default class",
              qdisc->dsc->name);
          qdisc->if_expr = data_unum(0);
          qdisc->dsc->default_class(&qdisc->if_expr,qdisc);
          assert(qdisc->if_expr.op &&
            qdisc->if_expr.op->dsc == &op_logical_or);
          tmp = qdisc->if_expr.op->b;
          data_destroy_1(qdisc->if_expr.op->a);
          data_destroy_1(qdisc->if_expr);
          qdisc->if_expr = tmp;
      }
    }
}


void dump_if_ext_global(FILE *file)
{
    dump_offsets(file); /* @@@ may dump unused offsets */
    dump_buckets(file); /* @@@ may dump unused buckets */
}


static void dump_if_ext_dump_actions_callback(const ELEMENT *e,void *user)
{
    DATA d = prm_data(e->params,&prm_if_expr);

    if (debug > 1) debug_expr("dump_if_ext_dump_actions_callback",d);
    dump_actions(d);
}


static int need_barrier;


static void dump_if_ext_dump_rules_callback(const ELEMENT *e,void *user)
{
    FILE *file = user;

    if (need_barrier) fprintf(file,"barrier\n");
    dump_rules(file,prm_data_ptr(e->params,&prm_if_expr));
    need_barrier = 1;
}


void dump_if_ext_local(const FILTER *filter,FILE *file)
{
    QDISC *qdisc = filter->parent.qdisc;
    DATA d = qdisc->if_expr;

    if (!use_bit_tree) {
      if (!no_combine) {
          dump_actions(d);
          write_actions(file,filter->parent.qdisc);
          dump_rules(file,&d);
      }
      else {
          iflib_comb_iterate(qdisc,dump_if_ext_dump_actions_callback,NULL);
          if (generate_default_class) dump_actions(d);
          write_actions(file,filter->parent.qdisc);
          need_barrier = 0;
          iflib_comb_iterate(qdisc,dump_if_ext_dump_rules_callback,file);
          if (generate_default_class) {
            if (need_barrier) fprintf(file,"barrier\n");
            dump_rules(file,&d);
          }
      }
      free_actions();
      return;
    }
    switch (alg_mode) {
      case 0:
          iflib_bit(file,filter->parent.qdisc,d);
          break;
      case 1:
          iflib_newbit(file,d);
          break;
      case 2:
          iflib_fastbit(file,d);
          break;
      default:
          errorf("unknown bit tree algorithm mode %d",alg_mode);
    }
}


static void dump_callback(FILE *file,void *user)
{
    const FILTER *filter = user;

    dump_pragma(file);
    dump_block(file,filter->parent.qdisc);
    dump_if_ext_prepare(filter);
    dump_if_ext_global(file);
    dump_if_ext_local(filter,file);
    reset_offsets();
}


void dump_if_ext(const FILTER *filter,const char *target)
{
    ext_build(target,NULL,filter,dump_callback,(void *) filter);
}

Generated by  Doxygen 1.6.0   Back to index