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

iflib_actdb.c

/*
 * ifact_db.c - Action database handling
 *
 * Written 2001,2002,2004 by Werner Almesberger
 * Copyright 2001,2002 by Bivio Networks, Network Robots
 * Copyright 2004 Werner Almesberger
 */


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#include "config.h"
#include "util.h"
#include "error.h"
#include "data.h"
#include "op.h"
#include "iflib.h"
#include "ext_all.h"


static struct action *root = NULL;


#define CLASS_TO_QDISC_NUM(c) ((c)->parent.qdisc->number)
#define CLASS_TO_DECISION(c) ((CLASS_TO_QDISC_NUM(c) << 16) | (c)->number)


/* ----- Step 1: Build the bit tree ---------------------------------------- */


static struct action *make_action(DATA d,struct action *parent)
{
    struct action *action;

    action = alloc_t(struct action);
    if (d.op && d.op->dsc == &op_conform) {
      action->type = at_conform;
      action->u.conform = d.op->a.u.police;
    }
    else if (d.op && d.op->dsc == &op_count) {
      action->type = at_count;
      action->u.count = d.op->a.u.police;
    }
    else if (!d.op && d.type == dt_decision) {
      switch (d.u.decision.result) {
          case dr_class:
            action->type = at_class;
            action->u.decision = d.u.decision.class;
            break;
          case dr_drop:
            action->type = at_drop;
            break;
          case dr_continue:
            action->type = at_unspec;
            break;
          default:
            dump_failed(d,"unsupported decision");
      }
    }
    else abort();
    action->parent = parent;
    action->c[0] = action->c[1] = NULL;
    action->number = -1;
    action->dumped = 0;
    action->next = NULL;
    action->referers = NULL;
    return action;
}


static struct action *add_actions(DATA d,DATA next,DATA otherwise,
  struct action *parent)
{
    struct action *action;

    if (debug > 1) debugf("add_actions");
    if (d.op && d.op->dsc == &op_logical_or) {
#if 0
      assert(!next.op && next.type == dt_none);
      assert(!otherwise.op && otherwise.type == dt_none);
#endif
      return add_actions(d.op->a,data_none(),d.op->b,parent);
    }
    if (d.op && d.op->dsc == &op_logical_and) {
#if 0
      assert(!next.op && next.type == dt_none); /* solution ? @@@ */
#endif
      return add_actions(d.op->a,d.op->b,otherwise,parent);
    }
    if (d.op && d.op->dsc == &op_conform) {
      action = make_action(d,parent);
      action->c[1] = add_actions(next,data_none(),otherwise,action);
      action->c[0] = add_actions(otherwise,data_none(),data_none(),action);
      return action;
    }
    if (d.op && d.op->dsc == &op_count) {
      action = make_action(d,parent);
      action->c[1] = add_actions(next,data_none(),otherwise,action);
      return action;
    }
    if (!d.op && d.type == dt_decision)
      return make_action(d,parent);
    dump_failed(d,"unknown action");
    return NULL; /* not reached */
}


/* ----- Step 2: Eliminate nodes repeating previous decisions -------------- */


static void free_1(struct action *a)
{
    free(a);
}


static void free_subtree(struct action *a)
{
    if (a) return;
    free_subtree(a->c[0]);
    free_subtree(a->c[1]);
    free_1(a);
}


static void repeated_actions(struct action *a)
{
    if (!a) return;
    if (a->type == at_conform) {
      struct action *walk;

      for (walk = a; walk; walk = walk->parent) {
          struct action **anchor;
          int value;

          if (!walk->parent || walk->parent->type != at_conform ||
            walk->parent->u.conform != a->u.conform)
            continue;
          value = walk->parent->c[0] == walk ? 0 : 1;
          anchor = a->parent->c[0] == a ? &a->parent->c[0] : &a->parent->c[1];
          *anchor = a->c[value];
          a->c[value]->parent = a->parent;
          free_subtree(a->c[1-value]);
          free_1(a);
          repeated_actions(*anchor);
          return;
      }
    }
    repeated_actions(a->c[0]);
    repeated_actions(a->c[1]);
}


/* ----- Hash table for leaf nodes ----------------------------------------- */


#define HASH_ENTRIES 47


static struct hash_list {
    struct action *action;
    struct hash_list *next;
} *hash[HASH_ENTRIES];


static int action_eq(const struct action *a,const struct action *b)
{
    if (a->type != b->type) return 0;
    switch (a->type) {
      case at_class:
          return a->u.decision == b->u.decision;
      case at_drop:
      case at_unspec:
          return 1;
      case at_conform:
          return a->u.conform == b->u.conform;
      case at_count:
          return a->u.count == b->u.count;
      default:
          abort();
    }
}


static struct action *hash_find(struct action *a)
{
    struct hash_list *walk,*new;
    int key;

    assert(a->type == at_class || a->type == at_drop || a->type == at_unspec);
    key = a->type == at_class ?
      CLASS_TO_DECISION(a->u.decision) % HASH_ENTRIES : 0;
    for (walk = hash[key]; walk; walk = walk->next)
      if (action_eq(walk->action,a)) return walk->action;
    new = alloc_t(struct hash_list);
    new->action = a;
    new->next = hash[key];
    hash[key] = new;
    return a;
}


/* ----- Step 3: Merge common subtrees ------------------------------------- */


static void add_referer(struct action *action,struct action *referer)
{
    struct action_referer **here;

    for (here = &action->referers; *here; here = &(*here)->next);
    *here = alloc_t(struct action_referer);
    (*here)->action = referer;
    (*here)->next = NULL;
}


static struct action *unique_action(struct action *a);

static struct action *_unique_action(struct action *a)
{
    struct action_referer *referer,*walk;

    switch (a->type) {
      case at_class:
      case at_drop:
      case at_unspec:
          return hash_find(a);
      case at_conform:
          a->c[0] = unique_action(a->c[0]);
          a->c[1] = unique_action(a->c[1]);
          for (referer = a->c[0]->referers; referer; referer = referer->next)
            if (action_eq(referer->action,a))
                for (walk = a->c[1]->referers; walk; walk = walk->next)
                  if (referer->action == walk->action)
                      return referer->action;
          add_referer(a->c[0],a);
          add_referer(a->c[1],a);
          return a;
      case at_count:
          a->c[1] = unique_action(a->c[1]);
          for (referer = a->c[1]->referers; referer; referer = referer->next)
            if (action_eq(referer->action,a)) return referer->action;
          add_referer(a->c[1],a);
          return a;
      default:
          abort();
    }
}


static struct action *unique_action(struct action *a)
{
    struct action *w;

    if (debug > 2) {
      for (w = a; w; w = w->parent) fprintf(stderr,"  ");
      fprintf(stderr,"ENTER unique_action: %p\n",a);
    }
    a = _unique_action(a);
    if (debug > 2) {
      for (w = a; w; w = w->parent) fprintf(stderr,"  ");
      fprintf(stderr,"EXIT unique_action: %p\n",a);
    }
    return a;
}


static void to_unique(struct action *a)
{
    struct action *res,*walk;

    res = unique_action(a);
    for (walk = root; walk; walk = walk->next)
      if (res == walk) return;
    res->next = root;
    root = res;
}


/* ----- Dump a subtree ---------------------------------------------------- */


static void dump_items(FILE *file,QDISC *qdisc,const struct action *a,int top)
{
    if (a->number != -1 && !top) {
      fprintf(file," action %d",a->number);
      return;
    }
    switch (a->type) {
      case at_conform:
          fprintf(file," conform %u",(unsigned) a->u.conform->number);
          dump_items(file,qdisc,a->c[1],0);
          dump_items(file,qdisc,a->c[0],0);
          break;
      case at_count:
          fprintf(file," count %u",(unsigned) a->u.count->number);
          dump_items(file,qdisc,a->c[1],0);
          break;
      case at_class:
          if (dump_all_decision(file,qdisc,a->u.decision->number)) break;
          fprintf(file," class %u:%u",CLASS_TO_QDISC_NUM(a->u.decision),
            a->u.decision->number);
          break;
      case at_drop:
          fprintf(file," drop");
          break;
      case at_unspec:
          fprintf(file," unspec");
          break;
      default:
          abort();
    }
}


static void dump_subtree(FILE *file,QDISC *qdisc,struct action *a,int top)
{
    switch (a->type) {
      case at_conform:
          dump_subtree(file,qdisc,a->c[0],0);
          /* fall through */
      case at_count:
          dump_subtree(file,qdisc,a->c[1],0);
          /* fall through */
      case at_class:
      case at_drop:
      case at_unspec:
          break;
      default:
          abort();
    }
    if (!a->dumped) {
      a->dumped = 1;
      fprintf(file,"action %d =",a->number);
      dump_items(file,qdisc,a,1);
      fputc('\n',file);
    }
}


#define INITIAL_PREFERRED_SIZE 8

static int *preferred_table; /* table of registered preferred numbers */
static int max_preferred; /* current array size */
static int preferred; /* number registered preferred numbers */


static void init_preferred(void)
{
    debugf2("init_preferred");
    max_preferred = INITIAL_PREFERRED_SIZE;
    preferred_table = alloc(max_preferred*sizeof(int));
    preferred = 0;
}


static void add_preferred(int index)
{
    debugf2("add_preferred(%d)",index);
    preferred_table[preferred++] = index;
    if (preferred == max_preferred) {
      max_preferred *= 2;
      preferred_table = realloc(preferred_table,max_preferred*sizeof(int));
      if (!preferred_table) {
          perror("realloc");
          exit(1);
      }
    }
}


static void sort_preferred(void)
{
    debugf2("sort_preferred[preferred %d]",preferred);
    preferred_table[preferred] = -1;
    qsort(preferred_table,preferred,sizeof(int),&comp_int);
    preferred = 0; /* use as pointer now */
}


static void release_preferred(void)
{
    free(preferred_table);
}


static int number_available_slow(int index)
{
    int i;

    debugf2("number_available_slow(%d)",index);
    for (i = 0; i < preferred; i++)
      if (preferred_table[i] == index) return 0;
    return 1;
}


static int number_available_fast(int index)
{
    debugf2("number_available_fast(%d)[preferred %d]",index,preferred);
    if (preferred_table[preferred] != -1 &&
      preferred_table[preferred] < index)
      preferred++;
    debugf2("  ... [preferred %d -> %d]",preferred,preferred_table[preferred]);
    return preferred_table[preferred] != index;
}


static void assign_indices(const struct action *root,struct action *a,
  int preferred,int *index)
{
    switch (a->type) {
      case at_conform:
          assign_indices(root,a->c[0],preferred,index);
          /* fall through */
      case at_count:
          assign_indices(root,a->c[1],preferred,index);
          /* fall through */
      case at_drop:
      case at_unspec:
          break;
      case at_class:
          if (a->number == -1 && preferred &&
            number_available_slow(a->u.decision->number & 0xff)) {
            a->number = a->u.decision->number & 0xff;
            add_preferred(a->number);
          }
          break;
      default:
          abort();
    }
    if (a->number != -1 || preferred) return;
    while (!number_available_fast(*index)) (*index)++;
    a->number = (*index)++;
}


/* ----- Debugging tree dump ----------------------------------------------- */


static void debug_subtree(FILE *file,const struct action *a,int level)
{
    const struct action_referer *r;

    fprintf(file,"%*s[%p] %d ",level*4,"",a,a->number);
    switch (a->type) {
      case at_conform:
          fprintf(file,"conform %u (0, then 1)\n",
            (unsigned) a->u.conform->number);
          break;
      case at_count:
          fprintf(file,"count %u\n",(unsigned) a->u.count->number);
          break;
      case at_class:
          fprintf(file,"class %u:%u\n",
            (unsigned) CLASS_TO_QDISC_NUM(a->u.decision),
            (unsigned) a->u.decision->number);
          break;
      case at_drop:
          fprintf(file,"drop\n");
          break;
      case at_unspec:
          fprintf(file,"unspec\n");
          break;
      default:
          abort();
    }
    fprintf(file,"%*s| parent %p, next %p\n",level*4,"",a->parent,a->next);
    fprintf(file,"%*s| referers:",level*4,"");
    for (r = a->referers; r; r = r->next)
      fprintf(file," %p",r->action);
    fputc('\n',file);
    switch (a->type) {
      case at_conform:
          debug_subtree(file,a->c[0],level+1);
          /* fall through */
      case at_count:
          debug_subtree(file,a->c[1],level+1);
          /* fall through */
      case at_class:
      case at_drop:
      case at_unspec:
          break;
      default:
          abort();
    }
}


static void debug_action_tree(FILE *file)
{
    struct action *walk;

    for (walk = root; walk; walk = walk->next)
      debug_subtree(file,walk,0);
}


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


void register_actions(DATA d)
{
    struct action *action;

    action = add_actions(d,data_none(),data_none(),NULL);
    repeated_actions(action);
    to_unique(action);
}


void write_actions(FILE *file,QDISC *qdisc)
{
    int index = 0;
    struct action *walk;

    init_preferred();
    /* assign preferred numbers */
    for (walk = root; walk; walk = walk->next)
      assign_indices(root,walk,1,&index);
    sort_preferred();
    /* assign all other numbers */
    for (walk = root; walk; walk = walk->next)
      assign_indices(root,walk,0,&index);
    /* dump the thing */
    for (walk = root; walk; walk = walk->next)
      dump_subtree(file,qdisc,walk,1);
    release_preferred();
}


const struct action *get_action(DATA d)
{
    struct action *action;

    if (debug > 1) debug_action_tree(stderr);
    action = add_actions(d,data_none(),data_none(),NULL);
    repeated_actions(action);
    if (debug > 1) fprintf(stderr,"in-action %p\n",action);
    action = unique_action(action);
    if (debug > 1) {
      fprintf(stderr,"out-action %p\n",action);
      print_expr(stderr,d);
    }
    return action;
}


int action_number(DATA d)
{
    return get_action(d)->number;
}


void free_actions(void)
{
    /* tricky: walk tree while == 1 referer */
    root = NULL;
    memset(hash,0,sizeof(hash));
    /*
     * @@@ Okay, this is a rather crude hack. But since all this code is doomed
     * anyway, it's pretty pointless to try to make it neat and tidy.
     */
}

Generated by  Doxygen 1.6.0   Back to index