git.sip-router.org Git - kamailio/blob - src/modules/pike/ip_tree.c

   1 /*
   2  * Copyright (C) 2001-2003 FhG Fokus
   3  *
   4  * This file is part of Kamailio, a free SIP server.
   5  *
   6  * Kamailio is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License as published by
   8  * the Free Software Foundation; either version 2 of the License, or
   9  * (at your option) any later version
  10  *
  11  * Kamailio is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  19  *
  20  */
  21
  22
  23 #include <stdio.h>
  24 #include <stdlib.h>
  25 #include <string.h>
  26 #include <unistd.h>
  27 #include <assert.h>
  28
  29 #include "../../core/dprint.h"
  30 #include "../../core/mem/shm_mem.h"
  31 #include "ip_tree.h"
  32
  33
  34
  35 static pike_ip_tree_t*  pike_root = 0;
  36
  37
  38 static inline pike_ip_node_t* prv_get_tree_branch(unsigned char b)
  39 {
  40         return pike_root->entries[b].node;
  41 }
  42
  43
  44 /* locks a tree branch */
  45 static inline void prv_lock_tree_branch(unsigned char b)
  46 {
  47         lock_set_get(pike_root->entry_lock_set, pike_root->entries[b].lock_idx);
  48 }
  49
  50
  51
  52 /* unlocks a tree branch */
  53 static inline void prv_unlock_tree_branch(unsigned char b)
  54 {
  55         lock_set_release(pike_root->entry_lock_set, pike_root->entries[b].lock_idx);
  56 }
  57
  58
  59 /* wrapper functions */
  60 pike_ip_node_t* get_tree_branch(unsigned char b)
  61 {
  62         return prv_get_tree_branch(b);
  63 }
  64 void lock_tree_branch(unsigned char b)
  65 {
  66         prv_lock_tree_branch(b);
  67 }
  68 void unlock_tree_branch(unsigned char b)
  69 {
  70         prv_unlock_tree_branch(b);
  71 }
  72
  73
  74 /* size must be a power of 2  */
  75 static gen_lock_set_t* init_lock_set(int *size)
  76 {
  77         gen_lock_set_t *lset;
  78
  79         lset=0; /* kill warnings */
  80         for( ; *size ; *size=((*size)>>1) ) {
  81                 LM_INFO("probing %d set size\n", *size);
  82                 /* create a lock set */
  83                 lset = lock_set_alloc( *size );
  84                 if (lset==0) {
  85                         LM_INFO("cannot get %d locks\n", *size);
  86                         continue;
  87                 }
  88                 /* init lock set */
  89                 if (lock_set_init(lset)==0) {
  90                         LM_INFO("cannot init %d locks\n", *size);
  91                         lock_set_dealloc( lset );
  92                         lset = 0;
  93                         continue;
  94                 }
  95                 /* alloc and init succesfull */
  96                 break;
  97         }
  98
  99         if (*size==0) {
 100                 LM_ERR("cannot get a lock set\n");
 101                 return 0;
 102         }
 103         return lset;
 104 }
 105
 106
 107
 108 /* Builds and Inits a new IP tree */
 109 int init_ip_tree(int maximum_hits)
 110 {
 111         int size;
 112         int i;
 113
 114         /* create the pike_root */
 115         pike_root = (pike_ip_tree_t*)shm_malloc(sizeof(pike_ip_tree_t));
 116         if (pike_root==0) {
 117                 LM_ERR("shm malloc failed\n");
 118                 goto error;
 119         }
 120         memset(pike_root, 0, sizeof(pike_ip_tree_t));
 121
 122         /* init lock set */
 123         size = MAX_IP_BRANCHES;
 124         pike_root->entry_lock_set = init_lock_set( &size );
 125         if (pike_root->entry_lock_set==0) {
 126                 LM_ERR("failed to create locks\n");
 127                 goto error;
 128         }
 129         /* assign to each branch a lock */
 130         for(i=0;i<MAX_IP_BRANCHES;i++) {
 131                 pike_root->entries[i].node = 0;
 132                 pike_root->entries[i].lock_idx = i % size;
 133         }
 134
 135         pike_root->max_hits = maximum_hits;
 136
 137         return 0;
 138 error:
 139         if (pike_root) {
 140                 shm_free(pike_root);
 141                 pike_root = NULL;
 142         }
 143         return -1;
 144 }
 145
 146 unsigned int get_max_hits()
 147 {
 148         return (pike_root != 0) ? pike_root->max_hits : -1;
 149 }
 150
 151 /* destroy an ip_node and all nodes under it; the nodes must be first removed
 152  * from any other lists/timers */
 153 static inline void destroy_ip_node(pike_ip_node_t *node)
 154 {
 155         pike_ip_node_t *foo, *bar;
 156
 157         foo = node->kids;
 158         while (foo){
 159                 bar = foo;
 160                 foo = foo->next;
 161                 destroy_ip_node(bar);
 162         }
 163
 164         shm_free(node);
 165 }
 166
 167
 168
 169 /* destroy and free the IP tree */
 170 void destroy_ip_tree(void)
 171 {
 172         int i;
 173
 174         if (pike_root==0)
 175                 return;
 176
 177         /* destroy and free the lock set */
 178         if (pike_root->entry_lock_set) {
 179                 lock_set_destroy(pike_root->entry_lock_set);
 180                 lock_set_dealloc(pike_root->entry_lock_set);
 181         }
 182
 183         /* destroy all the nodes */
 184         for(i=0;i<MAX_IP_BRANCHES;i++)
 185                 if (pike_root->entries[i].node)
 186                         destroy_ip_node(pike_root->entries[i].node);
 187
 188         shm_free( pike_root );
 189         pike_root = 0;
 190
 191         return;
 192 }
 193
 194
 195
 196 /* builds a new ip_node corresponding to a byte value */
 197 static inline pike_ip_node_t *new_ip_node(unsigned char byte)
 198 {
 199         pike_ip_node_t *new_node;
 200
 201         new_node = (pike_ip_node_t*)shm_malloc(sizeof(pike_ip_node_t));
 202         if (!new_node) {
 203                 LM_ERR("no more shm mem\n");
 204                 return 0;
 205         }
 206         memset( new_node, 0, sizeof(pike_ip_node_t));
 207         new_node->byte = byte;
 208         return new_node;
 209 }
 210
 211
 212
 213 /* splits from the current node (dad) a new child */
 214 pike_ip_node_t *split_node(pike_ip_node_t* dad, unsigned char byte)
 215 {
 216         pike_ip_node_t *new_node;
 217
 218         /* create a new node */
 219         if ( (new_node=new_ip_node(byte))==0 )
 220                 return 0;
 221         /* the child node inherits a part of his father hits */
 222         if (dad->hits[CURR_POS]>=1)
 223                 new_node->hits[CURR_POS] = (dad->hits[CURR_POS])-1;
 224         if (dad->leaf_hits[CURR_POS]>=1)
 225                 new_node->leaf_hits[PREV_POS] = (dad->leaf_hits[PREV_POS])-1;
 226         /* link the child into father's kids list -> insert it at the beginning,
 227          * is much faster */
 228         if (dad->kids) {
 229                 dad->kids->prev = new_node;
 230                 new_node->next = dad->kids;
 231         }
 232         dad->kids = new_node;
 233         new_node->branch = dad->branch;
 234         new_node->prev = dad;
 235
 236         return new_node;
 237 }
 238
 239
 240 #define is_hot_non_leaf(_node) \
 241         ( (_node)->hits[PREV_POS]>=pike_root->max_hits>>2 ||\
 242                 (_node)->hits[CURR_POS]>=pike_root->max_hits>>2 ||\
 243                 (((_node)->hits[PREV_POS]+(_node)->hits[CURR_POS])>>1)>=\
 244                         pike_root->max_hits>>2 )
 245
 246 #define is_hot_leaf(_node) \
 247         ( (_node)->leaf_hits[PREV_POS]>=pike_root->max_hits ||\
 248                 (_node)->leaf_hits[CURR_POS]>=pike_root->max_hits ||\
 249                 (((_node)->leaf_hits[PREV_POS]+(_node)->leaf_hits[CURR_POS])>>1)>=\
 250                         pike_root->max_hits )
 251
 252 #define is_warm_leaf(_node) \
 253         ( (_node)->hits[CURR_POS]>=pike_root->max_hits>>2 )
 254
 255 #define MAX_TYPE_VAL(_x) \
 256         (( (1<<(8*sizeof(_x)-1))-1 )|( (1<<(8*sizeof(_x)-1)) ))
 257
 258
 259 int is_node_hot_leaf(pike_ip_node_t *node)
 260 {
 261         return is_hot_leaf(node);
 262 }
 263
 264 /*! \brief Used by the rpc function */
 265 char *node_status_array[] = {"", "WARM", "HOT", "ALL"};
 266 pike_node_status_t node_status(pike_ip_node_t *node)
 267 {
 268         if ( is_hot_leaf(node) )
 269                 return NODE_STATUS_HOT;
 270
 271         if ( is_warm_leaf(node) )
 272                 return NODE_STATUS_WARM;
 273
 274         return NODE_STATUS_OK;
 275 }
 276
 277
 278
 279 /* mark with one more hit the given IP address - */
 280 pike_ip_node_t* mark_node(unsigned char *ip,int ip_len,
 281                                                         pike_ip_node_t **father,unsigned char *flag)
 282 {
 283         pike_ip_node_t *node;
 284         pike_ip_node_t *kid;
 285         int    byte_pos;
 286
 287         kid = pike_root->entries[ ip[0] ].node;
 288         node = 0;
 289         byte_pos = 0;
 290
 291         LM_DBG("search on branch %d (top=%p)\n", ip[0],kid);
 292         /* search into the ip tree the longest prefix matching the given IP */
 293         while (kid && byte_pos<ip_len) {
 294                 while (kid && kid->byte!=(unsigned char)ip[byte_pos]) {
 295                                 kid = kid->next;
 296                 }
 297                 if (kid) {
 298                         node = kid;
 299                         kid = kid->kids;
 300                         byte_pos++;
 301                 }
 302         }
 303
 304         LM_DBG("only first %d were matched!\n",byte_pos);
 305         *flag = 0;
 306         *father = 0;
 307
 308         /* what have we found? */
 309         if (byte_pos==ip_len) {
 310                 /* we found the entire address */
 311                 node->flags |= NODE_IPLEAF_FLAG;
 312                 /* increment it, but be careful not to overflow the value */
 313                 if(node->leaf_hits[CURR_POS]<MAX_TYPE_VAL(node->leaf_hits[CURR_POS])-1)
 314                         node->leaf_hits[CURR_POS]++;
 315                 /* becoming red node? */
 316                 if ( (node->flags&NODE_ISRED_FLAG)==0 ) {
 317                         if (is_hot_leaf(node) ) {
 318                                 *flag |= RED_NODE|NEWRED_NODE;
 319                                 node->flags |= NODE_ISRED_FLAG;
 320                         }
 321                 } else {
 322                         *flag |= RED_NODE;
 323                 }
 324         } else if (byte_pos==0) {
 325                 /* we hit an empty branch in the IP tree */
 326                 assert(node==0);
 327                 /* add a new node containing the start byte of the IP address */
 328                 if ( (node=new_ip_node(ip[0]))==0)
 329                         return 0;
 330                 node->hits[CURR_POS] = 1;
 331                 node->branch = ip[0];
 332                 *flag = NEW_NODE ;
 333                 /* set this node as pike_root of the branch starting with first byte of IP*/
 334                 pike_root->entries[ ip[0] ].node = node;
 335         } else{
 336                 /* only a non-empty prefix of the IP was found */
 337                 if ( node->hits[CURR_POS]<MAX_TYPE_VAL(node->hits[CURR_POS])-1 )
 338                         node->hits[CURR_POS]++;
 339                 if ( is_hot_non_leaf(node) ) {
 340                         /* we have to split the node */
 341                         *flag = NEW_NODE ;
 342                         LM_DBG("splitting node %p [%d]\n",node,node->byte);
 343                         *father = node;
 344                         node = split_node(node,ip[byte_pos]);
 345                 } else {
 346                         /* to reduce memory usage, force to expire non-leaf nodes if they
 347                          * have just a few hits -> basically, don't update the timer for
 348                          * them the nr of hits is small */
 349                         if ( !is_warm_leaf(node) )
 350                                 *flag = NO_UPDATE;
 351                 }
 352         }
 353
 354         return node;
 355 }
 356
 357
 358
 359 /* remove and destroy a IP node along with its subtree */
 360 void remove_node(pike_ip_node_t *node)
 361 {
 362         LM_DBG("destroying node %p\n",node);
 363         /* is it a branch pike_root node? (these nodes have no prev (father)) */
 364         if (node->prev==0) {
 365                 assert(pike_root->entries[node->byte].node==node);
 366                 pike_root->entries[node->byte].node = 0;
 367         } else {
 368                 /* unlink it from kids list */
 369                 if (node->prev->kids==node)
 370                         /* it's the head of the list! */
 371                         node->prev->kids = node->next;
 372                 else
 373                         /* it's somewhere in the list */
 374                         node->prev->next = node->next;
 375                 if (node->next)
 376                         node->next->prev = node->prev;
 377         }
 378
 379         /* destroy the node */
 380         node->next = node->prev = 0;
 381         destroy_ip_node(node);
 382 }
 383
 384 static void print_node(pike_ip_node_t *node,int sp, FILE *f)
 385 {
 386         pike_ip_node_t *foo;
 387
 388         /* print current node */
 389         if (!f) {
 390                 DBG("[l%d] node %p; brh=%d byte=%d flags=%d, hits={%d,%d} , "
 391                         "leaf_hits={%d,%d]\n",
 392                         sp, node, node->branch, node->byte, node->flags,
 393                         node->hits[PREV_POS],node->hits[CURR_POS],
 394                         node->leaf_hits[PREV_POS],node->leaf_hits[CURR_POS]);
 395         } else {
 396                 fprintf(f,"[l%d] node %p; brh=%d byte=%d flags=%d, hits={%d,%d} , "
 397                         "leaf_hits={%d,%d]\n",
 398                         sp, node, node->branch, node->byte, node->flags,
 399                         node->hits[PREV_POS],node->hits[CURR_POS],
 400                         node->leaf_hits[PREV_POS],node->leaf_hits[CURR_POS]);
 401         }
 402
 403         /* print all the kids */
 404         foo = node->kids;
 405         while(foo){
 406                 print_node(foo,sp+1,f);
 407                 foo = foo->next;
 408         }
 409 }
 410
 411 void print_tree(  FILE *f )
 412 {
 413         int i;
 414
 415         DBG("DEBUG:pike:print_tree: printing IP tree\n");
 416         for(i=0;i<MAX_IP_BRANCHES;i++) {
 417                 if (prv_get_tree_branch(i)==0)
 418                         continue;
 419                 prv_lock_tree_branch(i);
 420                 if (prv_get_tree_branch(i))
 421                         print_node( prv_get_tree_branch(i), 0, f);
 422                 prv_unlock_tree_branch(i);
 423         }
 424 }