Внедрение многобитового Trie в C

Question

Я получаю сообщение Ошибка сегментации: 11, когда я пытаюсь скомпилировать свой C-код с помощью gcc. Код реализует многобитовый алгоритм для поиска 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

Ваш nodes массив в node имеет место для 8 элементов, но в коде у вас есть максимально возможное значение 7. В результате, nodes[7] не дано значение, и будет иметь случайный мусор в нем, когда вы освобождаете узел с помощью free_mt (и в других местах, где вы ссылаетесь на этот элемент).