e8b93b84f2b527d1afbeddbfc5fb096b0de7cc2a
[kamailio] / 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 }