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

iptree.c

/*************************************************************************
***   Authentication, authorization, accounting + firewalling package
***   Copyright 1998-2002 Anton Vinokurov <anton@netams.com>
***   Copyright 2002-2008 NeTAMS Development Team
***   This code is GPL v3
***   For latest version and more info, visit this project web page
***   located at http://www.netams.com
***
*************************************************************************/
/* $Id: iptree.c,v 1.77 2008-02-23 08:35:03 anton Exp $ */

#include "netams.h"
#include "flow.h"
#include "iptree.h"

/////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////
IPTree::IPTree(u_char id) {
      nodes=1;
      dlink=0;
      unodes=0;
      instance=id;
      root=(IPTree_node*)aMalloc(sizeof(IPTree_node));
      netams_rwlock_init(&rwlock, NULL);
      aLog(D_INFO, "IP tree created\n");
}
/////////////////////////////////////////////////////////////////////////////////////////////
IPTree::~IPTree() {
      freetree(root);
      aFree(root);
      netams_rwlock_destroy(&rwlock);
      aLog(D_INFO, "IP tree destroyed\n");
}
/////////////////////////////////////////////////////////////////////////////////////////////
void IPTree::FreeTree(IPTree_node *node) {
        netams_rwlock_wrlock(&rwlock);
      freetree(node);
        netams_rwlock_unlock(&rwlock);
}
/////////////////////////////////////////////////////////////////////////////////////////////
void IPTree::freetree(IPTree_node *node) {
      if(node->next) {
            for(u_short i=0;i<256;i++) 
                  if(node->next[i]) freetree(node->next[i]);
            aFree(node->next);
                node->next=NULL;
                dlink--;
      }
      dsUlist *dsu;
      dsu=(dsUlist*)(node->ptr);
      if(dsu) {
            ELIST_FREE(dsu->list);
            aFree(dsu);
            unodes--;
      }
      if(node != root) {
            aFree(node); //we alloc root in constructor so we'll delete it in descructor
            nodes--;
      }
} 
/////////////////////////////////////////////////////////////////////////////////////////////
u_char IPTree::cleanup(IPTree_node *node) {
      unsigned short active=0;
      if(node->next) {
            for(u_short i=0;i<256;i++)
                  if(node->next[i]) 
                        if(cleanup(node->next[i])) active++;
                        else node->next[i]=NULL;

            if(!active) { 
                  aFree(node->next);
                  node->next=NULL;
                  dlink--;
            } else return 1;  
      }

      if(node->ptr) return 1;

        if(node != root) {
                aFree(node); //we alloc root in constructor so we'll delete it in destructor
                nodes--;
        }
      return 0;
}
/////////////////////////////////////////////////////////////////////////////////////////////
void IPTree::addr2tree(unsigned addr,u_char mask,NetUnit *u,u_char flag) {
      IPTree_node *node=root;
        IPTree_node *tmp;
        u_short num;
        int range;

      if(!addr && mask==32) return;

      netams_rwlock_wrlock(&rwlock);
        
      if(mask==0) {
            add2node(root,u,flag);
            netams_rwlock_unlock(&rwlock);
            return;
      }
      
//    struct in_addr ia;
//    ia.s_addr=addr;
//    aLog(D_INFO,"IPTree: working with %s /%u action=%u(1-add,0-remove)\n",inet_ ntoa(ia),mask,flag);

        for (u_char i=0;i<4;i++) {
                num=(u_char)(((char*)&addr)[i]);
//          aLog(D_INFO,"num[%u]=%u\n",i,num);
                range=((i+1)<<3)-mask;
                if(range<8 && range>=0){
                  u_short nnum=num;
                  if(!node->next){
                        if(!flag) break;
                                node->next=(IPTree_node**)aMalloc(256*sizeof(IPTree_node*));
                        dlink++;
                  }

                         do {
                                if(!node->next[num] && flag) {
                                        tmp=(IPTree_node*)aMalloc(sizeof(IPTree_node));
                                        node->next[num]=tmp;
                              tmp->up=node;
                              nodes++;
                                } 
                        add2node(node->next[num],u,flag);
                        num++;
                        } while(num<nnum+(u_char)(1<<range));
                        break;
                }
                  
            if(!node->next){
                        if(!flag) break;
                                node->next=(IPTree_node**)aMalloc(256*sizeof(IPTree_node*));
                        dlink++;
                }

            if(!node->next[num]) {
                  if(!flag) break; 
                  tmp=(IPTree_node*)aMalloc(sizeof(IPTree_node));
                        node->next[num]=tmp;
                  tmp->up=node;
                  nodes++;
                }
                node=node->next[num];
      }
      if(!flag) cleanup(root);
      
      netams_rwlock_unlock(&rwlock);
}

void IPTree::add2node(IPTree_node *node, NetUnit *u,u_char flag) {//1-add 0-remove
      if(!node) return; //just in case
      dsUlist *dsu=(dsUlist*)(node->ptr);

      if(flag) {//add
                  if(!dsu) {
                        dsu = (dsUlist*)aMalloc(sizeof(dsUlist));
                        node->ptr = dsu;
                        unodes++;
                  }
                  ELIST_ADD(dsu->list, u);
      } else {//remove
            ELIST_REMOVE(dsu->list, u);
            if(ELIST_IS_EMPTY(dsu->list)) { //empty
                  ELIST_FREE(dsu->list);
                  aFree(dsu);
                  unodes--;
                  node->ptr=NULL;
            }
      }
}
/////////////////////////////////////////////////////////////////////
dsUlist* IPTree::checktree(Flow *list, u_char check) {
        u_char num;
        IPTree_node *node=root;
      dsUlist *dsu;
      //if there is 0/0 network it will be included thus
      // otherwise ==NULL 
      dsUlist *start=(dsUlist*)(root->ptr);
      u_char *src,*dst;
      u_char i;
      const union attribute_value   *value;

      // some checking
      if((value = list->get(ATTR_IPV4_INFO)) == 0)
                  return start;

      if(start) start->mf[check]=MATCH_BOTH; // it's true for 0/0
      
      src=(u_char*)((char*)&value->ipv4_info.ip_src.s_addr);
      dst=(u_char*)((char*)&value->ipv4_info.ip_dst.s_addr);
//    aLog(D_INFO,"src=%s %s\n",inet_ ntoa(packet->ip_src),binary(src));
//    aLog(D_INFO,"dst=%s %s\n",inet_ ntoa(packet->ip_dst),binary(dst));

//    showtree(root,0,0);
      
      //check for dst first
        for ( i=0;i<4;i++) {
            num=dst[i];
//                aLog(D_INFO,"num[%u]=%u\n",i,num);
                if(!node->next || !node->next[num]) break;
                node=node->next[num];
                if(node->ptr) {
                  dsu=(dsUlist*)(node->ptr);
                  dsu->mf[check]=MATCH_DST;
                  dsu->link[check]=start;
                  start=dsu;
//                aLog(D_INFO,"MATCH_DST\n");
            }
        }
// i'll put comments here 
// there is trick in creating units list here and later when we using it:
// first cycle creates list of units lists 
// second - continues it for dst packet addr and if some units already matched in this list 
// rematch it as MATCH_BOTH, but !!! there is some units = networks that actually matches one unit net, 
// but represented with number of subnets with full mask (8,16,24,32) and cluster units
// in this case one unit will be represented in this list 2 times: once as MATCH_SRC and another MATCH_DST
// this is discussed and solved by PR 59: http://www.netams.com/mantis/view_bug_page.php?f_id=0000059
//
      node=root;
      //check for src
      for ( i=0;i<4;i++) {
            num=src[i];
//                aLog(D_INFO,"num[%u]=%u\n",i,num);
                if(!node->next || !node->next[num]) break;
                node=node->next[num];
                if(node->ptr) {
                  dsu=(dsUlist*)(node->ptr);
                  if(dsu->mf[check]) 
                        dsu->mf[check]=MATCH_BOTH;
                  else {
                        dsu->mf[check]=MATCH_SRC;
                        dsu->link[check]=start;
                              start=dsu;
                  }
//                aLog(D_INFO,"MATCH_SRC\n");
                }
        }
      
      return start;
}
/////////////////////////////////////////////////////////////////////
void IPTree::showtree(IPTree_node *node,unsigned addr,u_char depth) {
        u_short i;

        if(node->ptr) {
                struct in_addr ia;
                ia.s_addr=addr;
            char buffer[32];
                aLog(D_INFO,"%s /%u\n", inet_ntop(AF_INET, &ia, buffer, 32), depth<<3);
        } else {
            if(node->next)
                  for(i=0;i<256;i++)
                              if(node->next[i])  showtree(node->next[i],addr+(i<<(depth<<3)),depth+1);
        }
}
/////////////////////////////////////////////////////////////////////////////////////////////
void IPTree::ACCT(Flow *flow) {
        NetUnit *u;
        dsUlist *dsu;
        match mf;
        oid au_parent_id=0;
        match auto_unit_mf, units_mf;
      const union attribute_value   *value;
      
      auto_unit_mf=units_mf=MATCH_NONE;

        netams_rwlock_rdlock(&rwlock);

        //here we organize units that matches packet
        dsu=checktree(flow,CHECK_ACCT);
        
      for(;dsu!=NULL;dsu=dsu->link[CHECK_ACCT]) {
                  mf=dsu->mf[CHECK_ACCT];
            
                  ELIST_FOR_EACH(dsu->list, u) {
                  //check packet might be processed incorrectly due to wrong match flag
                  if(u->flags&NETUNIT_BROKEN_ACCT_MF) {
                        match mmf=u->Check(flow);
                        if(mmf!=mf && mf==MATCH_DST)
                              continue;
                        mf=mmf;
                  } else
                        mf=dsu->mf[CHECK_ACCT];

                  // now check the acct policy for this packet, and update counters
                  DSacct(u, flow, mf);
                  
                  //this is part of auto-units
                  if(u->type==NETUNIT_NET && ((NetUnit_net*)u)->auto_units_id) {
                        au_parent_id=u->id;
                        auto_unit_mf=mf;
                  } 
                  else if(u->type==NETUNIT_HOST || u->type==NETUNIT_USER) {
                        units_mf|=mf; //unit already exist
                  }
                  }
            dsu->mf[CHECK_ACCT]=MATCH_NONE;
        }
        netams_rwlock_unlock(&rwlock);

      value = flow->get(ATTR_IPV4_INFO);  
      if((auto_unit_mf&=~units_mf) && value != 0) {
            if(auto_unit_mf&MATCH_SRC) CreateAutoUnit(au_parent_id, value->ipv4_info.ip_src);
            if(auto_unit_mf&MATCH_DST) CreateAutoUnit(au_parent_id, value->ipv4_info.ip_dst);
      }
}

/////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////
// definitions for PrefixTree
/////////////////////////////////////////////////////////////////////////////////////////////
PrefixTree::PrefixTree() {
      nodes=1;
      dlink=0;
        root=(IPTree_node*)aMalloc(sizeof(IPTree_node));
}
/////////////////////////////////////////////////////////////////////////////////////////////
PrefixTree::~PrefixTree() {
        freetree(root);
      aFree(root);
}
/////////////////////////////////////////////////////////////////////////////////////////////
void PrefixTree::freetree(IPTree_node *node) {
        if(node->next) {
            for(u_short i=0;i<256;i++)
                  if(node->next[i]) freetree(node->next[i]);
            aFree(node->next);
            node->next=NULL;
            dlink--;
      }
      if(node !=root) {
            aFree(node);
            nodes--;
      }
}
/////////////////////////////////////////////////////////////////////////////////////////////
void PrefixTree::prefix2tree(net_prefix *p) {
        IPTree_node *tmp;
      IPTree_node *node=root;
        u_short num;
        int range;
      net_prefix *old;
        u_char mask=p->mask;
        u_char* addr=(u_char*)((char*)&p->network.s_addr);

        if(mask > 32) return;
        if(mask==0) node->ptr=(void*)p;

        for (u_char i=0;i<4;i++) {
                num=addr[i];
                range=((i+1)<<3)-mask;
                if(range<8 && range>=0){
                  u_short nnum=num;
                  if(!node->next){
                                node->next=(IPTree_node**)aMalloc(256*sizeof(IPTree_node*));
                        dlink++;
                        }
             
                        do {
                                if(!node->next[num]) {
                                        tmp=(IPTree_node*)aMalloc(sizeof(IPTree_node));
                                        node->next[num]=tmp;
                              nodes++;
                                } else if((old=(net_prefix*)node->next[num]->ptr)) {
                              if(old->mask > p->mask) 
                                    goto NEXT; // previous has higer mask
                              else if (old->mask == p->mask &&
                                    old->flags!=p->flags) {
                                    char buf1[32], buf2[32];
                                    inet_ntop(AF_INET, &(p->network), buf1, 32);
                                    inet_ntop(AF_INET, &(old->network), buf2, 32);
                                    aLog(D_WARN, "Prefix %s%s/%u conflicts with %s%s/%u, using 1st\n",
                                          (p->flags&PREFIX_INVERTED)?"!":"",buf1,p->mask,
                                          (old->flags&PREFIX_INVERTED)?"!":"",buf2,old->mask);
                                    return;
                              }
                        }
                                node->next[num]->ptr=(void*)p;
NEXT:                   
                        num++;
                        } while(num<nnum+(1<<range)); 
                        break;
                }
                
            if(!node->next){
                        node->next=(IPTree_node**)aMalloc(256*sizeof(IPTree_node*));
                  dlink++;
                }

            if(!node->next[num]) {
                        tmp=(IPTree_node*)aMalloc(sizeof(IPTree_node));
                        node->next[num]=tmp;
                  nodes++;
                }
                node=node->next[num];
        }
}
/////////////////////////////////////////////////////////////////////////////////////////////
u_char PrefixTree::checktree(unsigned addr) { 
        u_char num;
      IPTree_node *node=root;

        for (u_char i=0;i<4;i++) {
            num=(u_char)((char*)&addr)[i];
                if(!node->next || !node->next[num]) break;
                node=node->next[num];
        }
      
      if(node->ptr) {
            net_prefix *p=(net_prefix*)node->ptr;
            p->match++;
            if(!(p->flags&PREFIX_INVERTED)) return 1;
      }

        return 0;
}
/////////////////////////////////////////////////////////////////////////////////////////////
// below needed for FW and ACCTcheck
/////////////////////////////////////////////////////////////////////////////////////////////
void IPTree::DSacct(NetUnit *u, Flow *flow, match mf){
      if(!u->ap) return;

      policy_data *cpd;
      u_char monitor=0;
//    u_char monitor_because_of_layer7=0;
      
      aDebug(DEBUG_DS_IP, " policy_check for unit: %s (oid=%06X) ---\n", u->name, u->id);
      
      //we ensure nobody reads or writes through this unit 
      netams_rwlock_wrlock(&u->ap->rwlock);
      for (cpd=u->ap->root; cpd!=NULL; cpd=cpd->next) {
            cpd->check++;
            if(cpd->policy->Check(flow, mf)) {
                  if (!(cpd->policy_flags&POLICY_FLAG_INV)) {
                        cpd->match++;
                        monitor=1;
                        PolicyDataUpdate(mf, cpd, flow);
//                      if (cpd->policy->target.target_type&PT_LAYER7) {
//                            struct layer7_info_value *layer7_info=(struct layer7_info_value*)flow->get(ATTR_LAYER7_INFO);
//                            if (layer7_info) 
//                                  if (layer7_info->value) monitor_because_of_layer7=1;
//                      }
                        if (cpd->policy_flags&POLICY_FLAG_BRK) break;
                  }
            } else {
                  if (cpd->policy_flags&POLICY_FLAG_INV) {
                        cpd->match++;
                        monitor=1;
                        PolicyDataUpdate(mf, cpd, flow);
                        if (cpd->policy_flags&POLICY_FLAG_BRK) break;
                  }
            }
      }
      netams_rwlock_unlock(&u->ap->rwlock);

      // and for all parents
      NetUnit_group *gr;
      ELIST_FOR_EACH(u->parents, gr) {
            if (gr->checkDSList(instance))
                  DSacct(gr, flow, mf);
      }
      
//i dislike to monitor because of layer7
//better to monitor via policy - hope wthis will be done
      if(monitor && !ELIST_IS_EMPTY(u->monitors)) {
            Service *s;
            ELIST_FOR_EACH(u->monitors, s)
                  ((Service_Monitor_Interface*)s)->aMonitor(u, flow);
      }
}
/////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////

Generated by  Doxygen 1.6.0   Back to index