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

iflib_fastbit.c

/*
 * iflib_fastbit.c - FSM based on single-bit decisions (even more improved
 *               version)
 *
 * Written 2001,2002 by Werner Almesberger
 * Copyright 2001 Network Robots
 * Copyright 2002 Bivio Networks, Network Robots, Werner Almesberger
 */


#include <stdint.h>
#include <stdlib.h>
#include <assert.h>

#include "util.h"
#include "error.h"
#include "data.h"
#include "op.h"
#include "tree.h"
#include "field.h"
#include "iflib.h"


typedef uint32_t NUMBER;

typedef struct _bit {
    NUMBER number;
    int mark;
    int ref;
    int index;
    struct _bit *next[2];
} BIT;


#define TAG_MASK  0xf0000000
#define VALUE_MASK      0x0fffffff

#define METER_TAG 0x40000000
#define DECISION_TAG    0x80000000
#define DROP_TAG  (DECISION_TAG | 0x00000000)
#define CLASS_TAG (DECISION_TAG | 0x10000000)
#define RECLASSIFY_TAG  (DECISION_TAG | 0x20000000)
#define CONTINUE_TAG    (DECISION_TAG | 0x30000000)

#define BIT_TO_NUMBER(offset_group,offset) \
  (((offset_group) << 16) | (offset))
#define CONFORM_TO_NUMBER(bucket) \
  (METER_TAG | (bucket << 1))
#define COUNT_TO_NUMBER(bucket) \
  (METER_TAG | (bucket << 1) | 1)
#define DECISION_TO_NUMBER(dec) \
  ((dec).result == dr_drop ? DROP_TAG : \
   (dec).result == dr_continue ? CONTINUE_TAG : \
   (dec).result == dr_class ? CLASS_TAG | (dec).class->number : \
   RECLASSIFY_TAG | (dec).class->number)


static int curr_mark = 1;
static int nodes = 0;

/* ----- */


static BIT *make_bit(unsigned long number,BIT *true,BIT *false)
{
    BIT *bit = alloc_t(BIT);

    bit->number = number;
    bit->mark = 0;
    bit->ref = 1;
    bit->index = -1;
    bit->next[0] = false;
    bit->next[1] = true;
    nodes++;
    return bit;
}


static BIT *get_bit(BIT *bit)
{
    if (bit) bit->ref++;
    return bit;
}


static void put_bit(BIT *bit)
{
    if (bit && !--bit->ref) {
      put_bit(bit->next[0]);
      put_bit(bit->next[1]);
      nodes--;
      free(bit);
    }
}


/* ----- DAG construction -------------------------------------------------- */


extern int get_offset_group(DATA d,int base); /* borrowing from if_ext.c */


static BIT *value_dag(int offset,uint32_t value,uint32_t mask,
  int length,BIT *true,BIT *false,int offset_group)
{
    BIT *last;
    int i;

    last = true;
    for (i = 0; i < length; i++)
      if ((mask >> i) & 1) {
          NUMBER number = BIT_TO_NUMBER(offset_group,length-i-1+offset*8);

          last = (value >> i) & 1 ? make_bit(number,last,get_bit(false)) :
            make_bit(number,get_bit(false),last);
      }
    put_bit(false);
    return last;
}


static BIT *eq_dag(DATA a,DATA b,BIT *true,BIT *false,int offset_group)
{
    uint32_t value;
    uint32_t field_mask = 0xffffffff,value_mask = 0xffffffff;
    int shift = 0; /* negative means shift value right */
    int constant = 0; /* 0: field content affects result; -1: always false;
                   1: always true */
    /*
     * We expect the expression to follow the following constraints:
     * - left-hand side must contain a packet data access
     * - the offsets must be constant (iflib_off does this for us)
     * - right-hand side must be a constant (iflib_arith does this)
     */
    if (b.op || b.type != dt_unum) dump_failed(b,"\"eq const\" expected");

    value = b.u.unum;
    while (!a.op || a.op->dsc != &op_access) {
      if (!a.op) dump_failed(a,"operator expected");
      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;
      }
      if (a.op->dsc == &op_shift_left || a.op->dsc == &op_shift_right) {
          int n;

          if (a.op->b.op || a.op->b.type != dt_unum)
            dump_failed(a,"bad shift");
          n = a.op->b.u.unum;
          if (a.op->dsc == &op_shift_left) {
            shift -= n;
            field_mask >>= n;
            value_mask >>= n;
          }
          else {
            shift += n;
            field_mask <<= n;
            value_mask <<= n;
          }
          a = a.op->a;
          continue;
      }
      if (a.op->dsc == &op_and) {
          if (!a.op->a.op && a.op->a.type == dt_unum) {
            b = a.op->a;
            a = a.op->b;
          }
          else {
            if (a.op->b.op || a.op->b.type != dt_unum)
                dump_failed(a,"bad shift");
            b = a.op->b;
            a = a.op->a;
          }
          field_mask &= b.u.unum;
          value_mask &= b.u.unum;
          continue;
      }
      dump_failed(a,"bad operator");
    }
    if (a.op->b.op || a.op->b.type != dt_unum) dump_failed(a,"bad offset");
    if (a.op->c.op || a.op->c.type != dt_unum) dump_failed(a,"bad size");
#if 0
fprintf(stderr,"value 0x%lx, shift %d\n",(unsigned long) value,shift);
#endif
    if (shift) {
      if (shift < 0) {
          if (value << (32+shift)) constant = -1;
          value >>= -shift;
      }
      else {
          if (value >> (32-shift)) constant = -1;
          value <<= shift;
      }
    }
#if 0
fprintf(stderr,"(field & 0x%lx) == (0x%lx & 0x%lx) [0x%lx]\n",
  (unsigned long) field_mask,(unsigned long) value,(unsigned long) value_mask,
  (unsigned long) (value & value_mask));
#endif
    if (a.op->c.u.unum != 32) field_mask &= (1 << a.op->c.u.unum)-1;
    if (!constant && (shift < -32 || shift > 32))
      constant = field_mask ? -1 : 1;
    if (!constant && (value & ~value_mask)) constant = -1;
    if (constant) {
      yywarnf("comparison is always %s",constant > 0 ? "true" : "false");
      if (constant > 0) {
          put_bit(false);
          return true;
      }
      else {
          put_bit(true);
          return false;
      }
    }
    return value_dag(a.op->b.u.unum,value & value_mask,field_mask,
      a.op->c.u.unum,true,false,offset_group);
}


static BIT *make_dag(DATA d,BIT *true,BIT *false,int offset_group)
{
    if (d.op) {
      if (d.op->dsc == &op_logical_or)
          return make_dag(d.op->a,true,
            make_dag(d.op->b,get_bit(true),false,offset_group),offset_group);
      if (d.op->dsc == &op_logical_and)
          return make_dag(d.op->a,
            make_dag(d.op->b,true,get_bit(false),offset_group),
            false,offset_group);
      if (d.op->dsc == &op_logical_not)
          return make_dag(d.op->a,false,true,offset_group);
      if (d.op->dsc == &op_field_root)
          return make_dag(d.op->a,true,false,
            d.op->b.u.field_root->offset_group);
      if (d.op->dsc == &op_offset)
          return make_dag(d.op->a,true,false,
            get_offset_group(d,offset_group));
      if (d.op->dsc == &op_count) {
          put_bit(false);
          return make_bit(COUNT_TO_NUMBER(d.op->a.u.police->number),true,
            NULL);
      }
      if (true == false) {
          put_bit(false);
          return true;
      }
      if (d.op->dsc == &op_eq)
          return eq_dag(d.op->a,d.op->b,true,false,offset_group);
      if (d.op->dsc == &op_conform)
          return make_bit(CONFORM_TO_NUMBER(d.op->a.u.police->number),true,
            false);
      dump_failed(d,"bad operator");
    }
    switch (d.type) {
      case dt_unum:
          if (d.u.unum) {
            put_bit(false);
            return true;
          }
          else {
            put_bit(true);
            return false;
          }
          break;
      case dt_decision:
          put_bit(true);
          put_bit(false);
          return make_bit(DECISION_TO_NUMBER(d.u.decision),NULL,NULL);
      default:
          dump_failed(d,"bad terminal");
    }
    abort(); /* not reached */
}


/* ----- Debugging output -------------------------------------------------- */


static int index;


static void do_dump_dag(FILE *file,BIT *bit)
{
    if (!bit || bit->index != -1) return;
    do_dump_dag(file,bit->next[0]);
    do_dump_dag(file,bit->next[1]);
    bit->index = index++;
    fprintf(file,"%5d: 0x%08x %5d %5d\n",bit->index,bit->number,
      bit->next[0] ? bit->next[0]->index : -1,
      bit->next[1] ? bit->next[1]->index : -1);
}


static void reset_index(BIT *bit)
{
    if (!bit || bit->index == -1) return;
    bit->index = -1;
    reset_index(bit->next[0]);
    reset_index(bit->next[1]);
}


static void dump_dag(FILE *file,BIT *dag)
{
    index = 0;
    do_dump_dag(file,dag);
    reset_index(dag);
}


/* ----- */

static void do_verify_dag(BIT *bit)
{
    if (!bit || bit->index != -1) return;
assert(!bit->next[0] || bit->number <= bit->next[0]->number);
assert(!bit->next[1] || bit->number <= bit->next[1]->number);
    do_verify_dag(bit->next[0]);
    do_verify_dag(bit->next[1]);
    bit->index = index++;
}


static void verify_dag(BIT *dag)
{
    index = 0;
    do_verify_dag(dag);
    reset_index(dag);
}

/* ----- Graphical debugging output ---------------------------------------- */


static void print_pad(FILE *file,unsigned n,char pad,int len)
{
    if (n > 10) print_pad(file,n/10,pad,len-1);
    else {
      while (len -- > 1) fputc(pad,file);
    }
    fputc('0'+(n % 10),file);
}


static void dag_2d(FILE *file,BIT *bit,int level,int first)
{
    int i;

    if (!bit) return;
    if (bit->index == -1) bit->index = index++;
    print_pad(file,bit->index,first ? '-' : ' ',3);
    fputc(':',file);
    switch (bit->number & TAG_MASK) {
      case 0:
          print_pad(file,bit->number & VALUE_MASK,'_',3);
          break;
      case METER_TAG:
          abort(); /* not yet supported @@@ */
      case DROP_TAG:
          fprintf(file,"drp");
          break;
      case CLASS_TAG:
          fprintf(file,"c");
          print_pad(file,bit->number & VALUE_MASK,'_',2);
          break;
      case RECLASSIFY_TAG:
          fprintf(file,"r");
          print_pad(file,bit->number & VALUE_MASK,'_',2);
          break;
      case CONTINUE_TAG:
          fprintf(file,"uns");
          break;
      default:
          abort();
    }
    if (!bit->next[1]) fprintf(file,"\n");
    else {
      fprintf(file,"-");
      dag_2d(file,bit->next[1],level+1,1);
    }
    if (bit->next[0]) {
      for (i = 0; i < level; i++) fprintf(file,"   |    ");
      fprintf(file,"   |\n");
      for (i = 0; i < level; i++) fprintf(file,"   |    ");
      dag_2d(file,bit->next[0],level,0);
    }
}


static void dump_dag_2d(FILE *file,BIT *dag)
{
    index = 0;
    dag_2d(file,dag,0,1);
    reset_index(dag);
}


/* ---- Sorting ------------------------------------------------------------ */


static void fix_edge(BIT *bit,int edge,NUMBER border,NUMBER sorted)
{
    BIT *clone[2];
    int i,j;

fprintf(stderr,"  fix_edge(bit %p[%x],edge %d)\n",bit,bit->number,edge);
    /* FIXME: this is verboten if bit->number as a side-effect */
    while (bit->number == bit->next[edge]->number) {
      BIT *next = bit->next[edge];

      bit->next[edge] = get_bit(next->next[edge]);
      put_bit(next);
      if (!bit->next[edge]) return;
    }
fprintf(stderr,"  from %p[%x](check %p[%x], border %x, sorted %x)\n",
  bit,bit->number,bit->next[edge],
  bit->next[edge]->number,border,sorted);
    if ((bit->number^bit->next[edge]->number) & sorted) return;
      /* link points to different partition */
    if (!(bit->number & border)) return;
      /* we're in the lower part */
    if (bit->next[edge]->number & border) return;
      /* next is in the higher part */

fprintf(stderr,"    next %p[%x]\n",bit->next[edge],bit->next[edge]->number);
    for (i = 0; i < 2; i++) {
      if (bit->next[edge]->next[i] == bit->next[1-edge]) {
fprintf(stderr,"      quick clone (%d)\n",i);
          clone[i] = get_bit(bit->next[1-edge]);
          //continue;
      }
      else {
          /* swap bits */
          clone[i] = alloc_t(BIT);
fprintf(stderr,"      slow clone (new[%d] %p)\n",i,clone[i]);
          nodes++;
          *clone[i] = *bit;
          clone[i]->ref = 1;
          clone[i]->next[edge] = get_bit(bit->next[edge]->next[i]);
          clone[i]->next[1-edge] = get_bit(bit->next[1-edge]);
      }
//fprintf("--- after cloning ---\n");
//dump_dag_2d(stdout,dag);
      /* fix anything we broke by swapping */
      for (j = 0; j < 2; j++)
          if (clone[i]->next[j] &&
            !((bit->number^clone[i]->number) & sorted) &&
            !((bit->number^clone[i]->next[j]->number) & sorted))
            fix_edge(clone[i],j,border,sorted);
//fprintf("--- after fixing ---\n");
//dump_dag_2d(stdout,dag);
    }
    bit->number = bit->next[edge]->number;
    bit->mark = bit->next[edge]->mark;
    put_bit(bit->next[0]);
    put_bit(bit->next[1]);
    bit->next[0] = clone[0];
    bit->next[1] = clone[1];
    for (j = 0; j < 2; j++)
      while (bit->number == bit->next[j]->number) {
          BIT *next = bit->next[j];

          bit->next[j] = get_bit(next->next[j]);
          put_bit(next);
          if (!bit->next[j]) return;
      }
//fprintf("--- end of fixing ---\n");
//dump_dag_2d(stdout,dag);
}


static void quick_dag(BIT *bit,NUMBER border,NUMBER sorted)
{
    int i;

    if (bit->mark == curr_mark) return;
    bit->mark = curr_mark;
fprintf(stderr,"quick_dag(bit %p[%x])\n",bit,bit->number);
#if 0
    for (i = 0; i < 2; i++)
      if (bit->next[i]) {
          quick_dag(bit->next[i],border,sorted);
          fix_edge(bit,i,border,sorted);
#endif
    for (i = 0; i < 2; i++)
      if (bit->next[i]) {
          quick_dag(bit->next[i],border,sorted);
      }
    for (i = 0; i < 2; i++)
      if (bit->next[i]) {
          fix_edge(bit,i,border,sorted);
    }
}


static void sort_dag(BIT *dag)
{
    int i;

    for (i = 31; i >= 0; i--) {
      print_timer("# iteration");
      printf("---- i = %d, %d nodes\n",i,nodes);
      dump_dag_2d(stdout,dag);
      quick_dag(dag,1 << i,0xfffffffe << i);
      curr_mark = !curr_mark;
    }
}


/* ----- Optimize DAG ------------------------------------------------------ */


// static void optimize_dag(


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


void iflib_fastbit(FILE *file,DATA d)
{
    BIT *dag;

    start_timer();
    dag = make_dag(d,NULL,NULL,0);
    print_timer("# after make_dag");
    dump_dag_2d(stdout,dag);
    sort_dag(dag);
    print_timer("# after sort_dag");
    dump_dag_2d(stdout,dag);
    verify_dag(dag);
    printf("---- %d nodes\n",nodes);
}

Generated by  Doxygen 1.6.0   Back to index