CでのMultibit Trieの実装

Question

gccを使用してCコードをコンパイルしようとするとSegmentation Fault：11が発生します。このコードでは、IPルックアップ用のマルチビットトライアルゴリズムを実装しています。

時にはコードが実行されることがありますが、ほとんどの場合、セグメント化エラーの問題が発生します。

#include <stdio.h> 
#include <stdlib.h> 
#include <arpa/inet.h> 
#include <math.h> 

/* nodes is an array 8 elements. Each element is a pointer to its child node.*/ 
/* stride has been taken as 3. therefore 2^3 = 8, the elements in a node */ 
struct Mt_Node{ 
    struct Mt_Node* nodes[8]; 
    int verdict; 
}; 

typedef struct Mt_Node node; 

/* Initialize the multibit trie node */ 
Mt_Node* init_mtnode(){ 
    node *ret; 
     int size; 
     ret = static_cast<node *>(malloc(sizeof(node))); 
     if (ret == NULL) /* check for NULL */ 
      return NULL; 
     size = 2 << 3; 
     if (size >= 8) 
      size = 7; /* maximum possible value */ 
     for (int i = 0 ; i < size ; ++i) 
       ret->nodes[i] = NULL; 
     ret->verdict = -1; 
     return ret; 
} 

/* Clean up Multibit Trie */ 
void free_mt(struct Mt_Node *root){ 
    for(int i=0; i<8; i++){ 
     if(root->nodes[i]){ 
     free_mt(root->nodes[i]); 
    } 

    } 
    free(root); 
} 

/* Insert a Rule */ 
void insert_rule(struct Mt_Node *root, uint32_t prefix, int prelen, int portnum){ 

    static int n_rules = 0; 
    n_rules ++; 

    /* default rule: if packet matches none of the rules, 
    * it will match this default rule, i.e. 0.0.0.0/0 */ 
    if(prelen == 0){ 
     root->verdict = portnum; 
     return; 
    }  

    uint32_t temp_prefix = prefix; 
    int curr_bits, curr_bits1; 
    Mt_Node  *curr_node = root; 

    if(prelen % 3 == 0){ 
     /* if the condition is 0, then this node will be used, 
     otherwise we will have to move to next node */ 

     for(int j=0; j<(prelen/3); j++){ 
      curr_bits = temp_prefix & 0xE0000000; 
      temp_prefix = curr_bits >> 29; 
      int index = (int) temp_prefix; 


      if(curr_node->nodes[index] == NULL){ 
       curr_node->nodes[index] = init_mtnode(); 
      } 

      curr_node = curr_node->nodes[index]; 
      temp_prefix=temp_prefix<<3; 
     } 

     curr_node->verdict = portnum; 

    } 

    else if(prelen % 3 == 1){ 

     int b = prelen/3; 
     int c = 1; 
     for (int i=0; i<b; i++){ 

      curr_bits = temp_prefix & 0xE0000000; 
      temp_prefix = curr_bits >> 29; 
      int index = (int) temp_prefix; 


      if(curr_node->nodes[index] == NULL){ 
       curr_node->nodes[index] = init_mtnode(); 
      } 

      curr_node = curr_node->nodes[index]; 
      temp_prefix=temp_prefix<<3; 

     } 

     curr_bits = (temp_prefix & 0x80000000)? 1 : 0; 
     if(curr_bits == 0){ 
      for(int z=0; z<4;z++){ 
       if(curr_node->nodes[z] == NULL){ 
       curr_node->nodes[z] = init_mtnode(); 
       (curr_node->nodes[z])->verdict = portnum; 
       } 
      } 
     } 

     else { 

      for(int z=4; z<8;z++){ 
       if(curr_node->nodes[z] == NULL){ 
       curr_node->nodes[z] = init_mtnode(); 
       (curr_node->nodes[z])->verdict = portnum; 
       } 
      } 
     } 

    } 

    else if(prelen % 3 == 2){ 

     int b = prelen/3; 
     int c = 0; 
     for (int i=0; i<b; i++){ 

      curr_bits = temp_prefix & 0xE0000000; 
      temp_prefix = curr_bits >> 29; 
      int index = (int) temp_prefix; 


      if(curr_node->nodes[index] == NULL){ 
       curr_node->nodes[index] = init_mtnode(); 
      } 

      curr_node = curr_node->nodes[index]; 
      temp_prefix=temp_prefix<<3; 

     } 

     curr_bits = temp_prefix & 0xc0000000; 
     curr_bits = curr_bits>>30; 
     int curr_bits1 = (int) curr_bits; 

     if(curr_bits1 == 0){ 
      for(int z=0; z<2;z++){ 
       if(curr_node->nodes[z] == NULL){ 
       curr_node->nodes[z] = init_mtnode(); 
       (curr_node->nodes[z])->verdict = portnum; 
      } 

     } 

    } 

     else if(curr_bits1 == 1){ 
      for(int z=2; z<4;z++){ 
       if(curr_node->nodes[z] == NULL){ 
       curr_node->nodes[z] = init_mtnode(); 
       (curr_node->nodes[z])->verdict = portnum; 
      } 


     } 

    } 

     else if(curr_bits1 == 2){ 
      for(int z=4; z<6;z++){ 
       if(curr_node->nodes[z] == NULL){ 
       curr_node->nodes[z] = init_mtnode(); 
       (curr_node->nodes[z])->verdict = portnum; 
      } 

     } 

    } 

     else { 

      for(int z=6; z<8;z++){ 
       if(curr_node->nodes[z] == NULL){ 
       curr_node->nodes[z] = init_mtnode(); 
       (curr_node->nodes[z])->verdict = portnum; 
      } 

     } 


    } 

} 

} 

int lookup_ip(Mt_Node *root, uint32_t ip) 
{ 
    uint32_t temp_prefix = ip; 
    Mt_Node  *curr_node = root; 
    int   curr_verdict = root->verdict; 
    int   curr_bit = 0; 
    int   curr_3bits = 0; 
    int   curr_bits1 = 0; 
    int b =0; 

    temp_prefix = temp_prefix & 0xE0000000; 
    temp_prefix = temp_prefix >> 29; 
    int index = (int) temp_prefix; 

     if(curr_node->nodes[index] == NULL){ 
      return curr_verdict; 
     } 

     while(curr_node->nodes[index] != NULL){ 

     curr_verdict = (curr_node->verdict == -1) ? curr_verdict : curr_node->verdict; 
     curr_node = curr_node->nodes[index]; 


     b += 3; 

     temp_prefix = (ip << b); 
     temp_prefix = temp_prefix & 0xE0000000; 
     temp_prefix = temp_prefix >> 29; 
     index = (int) temp_prefix; 

     } 


curr_verdict = (curr_node->verdict == -1) ? curr_verdict : curr_node->verdict; 
return curr_verdict ; 



} 

Answer 1

nodeであなたのnodes配列は、8つの要素のためのスペースを持っていますが、あなたのコードでは、あなたが、nodes[7]が値を与えられていない結果として7の可能な最大値を持っており、それ際にランダムなゴミを持っていますノードをfree_mt（およびその要素を参照する他の場所）で解放します。