all: updated FSF address in GPL text
[sip-router] / modules / carrierroute / cr_data.c
1 /*
2  * $Id$
3  *
4  * Copyright (C) 2007-2008 1&1 Internet AG
5  *
6  * This file is part of SIP-router, a free SIP server.
7  *
8  * SIP-router is free software; you can redistribute it and/or modify
9  * it under the terms of the GNU General Public License as published by
10  * the Free Software Foundation; either version 2 of the License, or
11  * (at your option) any later version
12  *
13  * SIP-router is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License 
19  * along with this program; if not, write to the Free Software 
20  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
21  */
22
23 /**
24  * \file cr_data.c
25  * \brief Contains the functions to manage routing data.
26  * \ingroup carrierroute
27  * - Module; \ref carrierroute
28  */
29
30 #include <stdlib.h>
31 #include "../../mem/shm_mem.h"
32 #include "cr_data.h"
33 #include "carrierroute.h"
34 #include "cr_config.h"
35 #include "cr_db.h"
36 #include "cr_carrier.h"
37 #include "cr_domain.h"
38 #include "cr_rule.h"
39
40
41 /**
42  * Pointer to the routing data.
43  */
44 struct route_data_t ** global_data = NULL;
45
46
47 static int carrier_data_fixup(struct route_data_t * rd){
48         int i;
49         str tmp;
50         tmp = default_tree;
51         rd->default_carrier_id = -1;
52         for(i=0; i<rd->carrier_num; i++){
53                 if(rd->carriers[i]){
54                         if(str_strcmp(rd->carriers[i]->name, &tmp) == 0){
55                                 rd->default_carrier_id = rd->carriers[i]->id;
56                         }
57                 }
58         }
59         if(rd->default_carrier_id < 0){
60                 LM_ERR("default_carrier not found\n");
61         }
62         return 0;
63 }
64
65
66 /**
67  * initialises the routing data, initialises the global data pointer
68  *
69  * @return 0 on success, -1 on failure
70  */
71 int init_route_data(void) {
72         if (global_data == NULL) {
73                 global_data = (struct route_data_t **)
74                               shm_malloc(sizeof(struct route_data_t *));
75                 if (global_data == NULL) {
76                         SHM_MEM_ERROR;
77                         return -1;
78                 }
79         }
80         *global_data = NULL;
81         return 0;
82 }
83
84
85 /**
86  * Frees the routing data
87  */
88 void destroy_route_data(void){
89         struct route_data_t * rd = get_data();
90         clear_route_data(rd);
91         if(global_data){
92                 *global_data = NULL;
93                 shm_free(global_data);
94                 global_data = NULL;
95         }
96 }
97
98
99 /**
100  * Clears the complete routing data.
101  *
102  * @param data route data to be cleared
103  */
104 void clear_route_data(struct route_data_t *data) {
105         int i;
106
107         if (data == NULL) {
108                 return;
109         }
110         if (data->carriers != NULL) {
111                 for (i = 0; i < data->carrier_num; ++i) {
112                         if (data->carriers[i] != NULL) {
113                                 destroy_carrier_data(data->carriers[i]);
114                         }
115                 }
116                 shm_free(data->carriers);
117         }
118         if (data->carrier_map) {
119                 for (i = 0; i < data->carrier_num; ++i) {
120                         if (data->carrier_map[i].name.s) shm_free(data->carrier_map[i].name.s);
121                 }
122                 shm_free(data->carrier_map);
123         }
124         if (data->domain_map) {
125                 for (i = 0; i < data->domain_num; ++i) {
126                         if (data->domain_map[i].name.s) shm_free(data->domain_map[i].name.s);
127                 }
128                 shm_free(data->domain_map);
129         }
130         shm_free(data);
131         return;
132 }
133
134
135 /**
136  * adds a carrier_data struct for given carrier.
137  *
138  * @param rd route data to be searched
139  * @param carrier_data the carrier data struct to be inserted
140  *
141  * @return 0 on success, -1 on failure
142  */
143 int add_carrier_data(struct route_data_t * rd, struct carrier_data_t * carrier_data) {
144         if (rd->first_empty_carrier >= rd->carrier_num) {
145                 LM_ERR("carrier array already full");
146                 return -1;
147         }
148
149         if (rd->carriers[rd->first_empty_carrier] != 0) {
150                 LM_ERR("invalid pointer in first empty carrier entry");
151                 return -1;
152         }
153
154         rd->carriers[rd->first_empty_carrier] = carrier_data;
155         rd->first_empty_carrier++;
156         return 0;
157 }
158
159
160 /**
161  * Loads the routing data into the routing trees and sets the
162  * global_data pointer to the new data. The old_data is removed
163  * when it is not locked anymore.
164  *
165  * @return 0 on success, -1 on failure
166  */
167 int reload_route_data(void) {
168         struct route_data_t * old_data;
169         struct route_data_t * new_data = NULL;
170         int i;
171
172         if ((new_data = shm_malloc(sizeof(struct route_data_t))) == NULL) {
173                 SHM_MEM_ERROR;
174                 return -1;
175         }
176         memset(new_data, 0, sizeof(struct route_data_t));
177
178         switch (mode) {
179         case CARRIERROUTE_MODE_DB:
180                 if (load_route_data_db(new_data) < 0) {
181                         LM_ERR("could not load routing data\n");
182                         goto errout;
183                 }
184                 break;
185         case CARRIERROUTE_MODE_FILE:
186                 if (load_config(new_data) < 0) {
187                         LM_ERR("could not load routing data\n");
188                         goto errout;
189                 }
190                 break;
191         default:
192                 LM_ERR("invalid mode");
193                 goto errout;
194         }
195         if (new_data == NULL) {
196                 LM_ERR("loading routing data failed (NULL pointer)");
197                 goto errout;
198         }
199
200         /* sort carriers by id for faster access */
201         qsort(new_data->carriers, new_data->carrier_num, sizeof(new_data->carriers[0]), compare_carrier_data);
202
203         /* sort domains by id for faster access */
204         for (i=0; i<new_data->carrier_num; i++) {
205                 qsort(new_data->carriers[i]->domains, new_data->carriers[i]->domain_num, sizeof(new_data->carriers[i]->domains[0]), compare_domain_data);
206         }
207
208         if (rule_fixup(new_data) < 0) {
209                 LM_ERR("could not fixup rules\n");
210                 goto errout;
211         }
212
213         if (carrier_data_fixup(new_data) < 0){
214                 LM_ERR("could not fixup trees\n");
215                 goto errout;
216         }
217
218         new_data->proc_cnt = 0;
219
220         if (*global_data == NULL) {
221                 *global_data = new_data;
222         } else {
223                 old_data = *global_data;
224                 *global_data = new_data;
225                 i = 0;
226                 while (old_data->proc_cnt > 0) {
227                         LM_ERR("data is still locked after %i seconds\n", i);
228                         sleep_us(i*1000000);
229                         i++;
230                 }
231                 clear_route_data(old_data);
232         }
233         return 0;
234
235  errout:
236         clear_route_data(new_data);
237         return -1;
238 }
239
240
241 /**
242  * Increases lock counter and returns a pointer to the
243  * current routing data
244  *
245  * @return pointer to the global routing data on success,
246  * NULL on failure
247 */
248 struct route_data_t * get_data(void) {
249         struct route_data_t *ret;
250         if (!global_data || !*global_data) {
251                 return NULL;
252         }
253         ret = *global_data;
254         lock_get(&ret->lock);
255         ++ret->proc_cnt;
256         lock_release(&ret->lock);
257         if (ret == *global_data) {
258                 return ret;
259         } else {
260                 lock_get(&ret->lock);
261                 --ret->proc_cnt;
262                 lock_release(&ret->lock);
263                 return NULL;
264         }
265 }
266
267
268 /**
269  * decrements the lock counter of the routing data
270  *
271  * @param data data to be released
272  */
273 void release_data(struct route_data_t *data) {
274         lock_get(&data->lock);
275         --data->proc_cnt;
276         lock_release(&data->lock);
277 }
278
279
280 /**
281  * Returns the carrier data for the given id by doing a binary search.
282  * @note The carrier array must be sorted!
283  *
284  * @param rd route data to be searched
285  * @param carrier_id the id of the desired carrier
286  *
287  * @return a pointer to the desired carrier data, NULL if not found.
288  */
289 struct carrier_data_t *get_carrier_data(struct route_data_t * rd, int carrier_id) {
290         struct carrier_data_t **ret;
291         struct carrier_data_t key;
292         struct carrier_data_t *pkey = &key;
293
294         if (!rd) {
295                 LM_ERR("NULL pointer in parameter\n");
296                 return NULL;
297         }
298         key.id = carrier_id;
299         ret = bsearch(&pkey, rd->carriers, rd->carrier_num, sizeof(rd->carriers[0]), compare_carrier_data);
300         if (ret) return *ret;
301         return NULL;
302 }
303
304
305 typedef int (*cmpfunc_t)(const void *v1, const void *v2);
306
307
308 /**
309  * Implements a binary search algorithm using the function cmpfunc
310  * for comparison.
311  *
312  * @param base pointer to the beginning of the array
313  * @param len length of array
314  * @param elemsize size of array elements
315  * @param key pointer to the key we are looking for
316  * @param cmpfunc function to be used for comparison
317  * @param index  If index is not NULL it is set to:
318  *     -1 if an error occured,
319  *     the index of the first entry equal to v
320  *     or the index of the first entry greater than v in the case v was not found.
321  *   Be careful: The index returned can be greater than the length of the array!
322  *
323  * @return -1 on error, 0 if the value was not found, 1 if it was found.
324  */
325 static int binary_search(void *base, unsigned int len, int elemsize, void *key, cmpfunc_t cmpfunc, int *index) {
326         int left, right, mid;
327
328         if (index) *index=-1;
329         if (!base) {
330                 LM_ERR("NULL pointer in parameter\n");
331                 return -1;
332         }
333         if (len == 0) {
334                 if (index) *index=0;
335                 return 0;
336         }
337
338         left=0;
339         right=len-1;
340         if (cmpfunc(base+elemsize*left, key) > 0) {
341                 LM_DBG("not found (out of left bound)\n");
342                 if (index) *index=0; /* not found, must be inserted at the beginning of array */
343                 return 0;
344         }
345         if (cmpfunc(base+elemsize*right, key) < 0) {
346                 LM_DBG("not found (out of right bound)\n");
347                 if (index) *index=len; /* not found, must be inserted at the end of array */
348                 return 0;
349         }
350
351         while (left < right) {
352                 mid = left + ((right - left) / 2);
353                 if (cmpfunc(base+elemsize*mid, key) < 0) left = mid + 1;
354                 else right = mid;
355         }
356
357         /* left == right here! */
358         if (index) *index=left;
359         if (cmpfunc(base+elemsize*left, key) == 0) return 1;
360         else return 0;
361 }
362
363
364 /**
365  * Returns the domain data for the given id by doing a binary search.
366  * If not found, a new domain data structure is added.
367  *
368  * @param rd route data to used for name - id mapping
369  * @param carrier_data carrier data to be searched
370  * @param domain_id the id of desired domain
371  *
372  * @return a pointer to the desired domain data, NULL on error.
373  */
374 static struct domain_data_t * get_domain_data_or_add(struct route_data_t * rd, struct carrier_data_t * carrier_data, int domain_id) {
375         struct domain_data_t key;
376         struct domain_data_t *pkey = &key;
377         struct domain_data_t *domain_data = NULL;
378         str *domain_name;
379         int i;
380         int res;
381
382         if ((!rd) || (!carrier_data)) {
383                 LM_ERR("NULL pointer in parameter\n");
384                 return NULL;
385         }
386
387         key.id = domain_id;
388         res = binary_search(carrier_data->domains, carrier_data->first_empty_domain, sizeof(struct domain_data_t *), &pkey, compare_domain_data, &i);
389         if (res<0) {
390                 LM_ERR("error while searching for domain_id %d\n", domain_id);
391                 return NULL;
392         }
393         else if (res>0) {
394                 /* found domain id */
395                 domain_data = carrier_data->domains[i];
396         }
397         else {
398                 /* did not find domain id - insert new entry! */
399                 if ((domain_name = map_id2name(rd->domain_map, rd->domain_num, domain_id)) == NULL) {
400                         LM_ERR("could not find domain name for id %d\n", domain_id);
401                         return NULL;
402                 }
403                 if ((domain_data = create_domain_data(domain_id, domain_name)) == NULL) {
404                         LM_ERR("could not create new domain data\n");
405                         return NULL;
406                 }
407
408                 /* keep the array sorted! */
409                 if (add_domain_data(carrier_data, domain_data, i) < 0) {
410                         LM_ERR("could not add domain data\n");
411                         destroy_domain_data(domain_data);
412                         return NULL;
413                 }
414                 LM_INFO("added domain %d '%.*s' to carrier %d '%.*s'", domain_id, domain_name->len, domain_name->s, carrier_data->id, carrier_data->name->len, carrier_data->name->s);
415         }
416
417         return domain_data;
418 }
419
420
421 /**
422  * Adds the given route information to the routing domain identified by
423  * domain. scan_prefix identifies the number for which the information
424  * is and the rewrite_* parameters define what to do in case of a match.
425  * prob gives the probability with which this rule applies if there are
426  * more than one for a given prefix.
427  *
428  * @param rd the route data to which the route shall be added
429  * @param carrier_id the carrier id of the route to be added
430  * @param domain_id the routing domain id of the new route
431  * @param scan_prefix the number prefix
432  * @param flags user defined flags
433  * @param mask mask for user defined flags
434  * @param max_targets the number of targets
435  * @param prob the weight of the rule
436  * @param rewrite_hostpart the rewrite_host of the rule
437  * @param strip the number of digits to be stripped off userpart before prepending prefix
438  * @param rewrite_local_prefix the rewrite prefix
439  * @param rewrite_local_suffix the rewrite suffix
440  * @param status the status of the rule
441  * @param hash_index the hash index of the rule
442  * @param backup indicates if the route is backed up by another. only 
443                  useful if status==0, if set, it is the hash value
444                  of another rule
445  * @param backed_up an -1-termintated array of hash indices of the route 
446                     for which this route is backup
447  * @param comment a comment for the route rule
448  *
449  * @return 0 on success, -1 on error in which case it LOGs a message.
450  */
451 int add_route(struct route_data_t * rd, int carrier_id,
452                 int domain_id, const str * scan_prefix, flag_t flags, flag_t mask, int max_targets,
453                 double prob, const str * rewrite_hostpart, int strip,
454                 const str * rewrite_local_prefix, const str * rewrite_local_suffix,
455                 int status, int hash_index, int backup, int * backed_up, const str * comment) {
456         struct carrier_data_t * carrier_data = NULL;
457         struct domain_data_t * domain_data = NULL;
458         LM_INFO("adding prefix %.*s, prob %f\n", scan_prefix->len, scan_prefix->s, prob);
459
460         if ((carrier_data = get_carrier_data(rd, carrier_id)) == NULL) {
461                 LM_ERR("could not retrieve carrier data for carrier id %d\n", carrier_id);
462                 return -1;
463         }
464
465         if ((domain_data = get_domain_data_or_add(rd, carrier_data, domain_id)) == NULL) {
466                 LM_ERR("could not retrieve domain data\n");
467                 return -1;
468         }
469
470         LM_INFO("found carrier and domain, now adding route\n");
471         return add_route_to_tree(domain_data->tree, scan_prefix, flags, mask, scan_prefix, max_targets, prob, rewrite_hostpart,
472                                  strip, rewrite_local_prefix, rewrite_local_suffix, status,
473                                  hash_index, backup, backed_up, comment);
474 }
475
476
477 /**
478  * Adds the given failure route information to the failure routing domain identified by
479  * domain. scan_prefix, host, reply_code and flags identifies the number for which
480  * the information is and the next_domain parameter defines where to continue routing
481  * in case of a match.
482  *
483  * @param rd the route data to which the route shall be added
484  * @param carrier_id the carrier id of the route to be added
485  * @param domain_id the routing domain id of the new route
486  * @param scan_prefix the number prefix
487  * @param host the hostname last tried
488  * @param reply_code the reply code 
489  * @param flags user defined flags
490  * @param mask for user defined flags
491  * @param next_domain_id continue routing with this domain id
492  * @param comment a comment for the failure route rule
493  *
494  * @return 0 on success, -1 on error in which case it LOGs a message.
495  */
496 int add_failure_route(struct route_data_t * rd, int carrier_id, int domain_id,
497                 const str * scan_prefix, const str * host, const str * reply_code,
498                 flag_t flags, flag_t mask, int next_domain_id, const str * comment) {
499         struct carrier_data_t * carrier_data = NULL;
500         struct domain_data_t * domain_data = NULL;
501         LM_INFO("adding prefix %.*s, reply code %.*s\n", scan_prefix->len, scan_prefix->s, reply_code->len, reply_code->s);
502                 
503         if (reply_code->len!=3) {
504                 LM_ERR("invalid reply_code '%.*s'!\n", reply_code->len, reply_code->s);
505                 return -1;
506         }
507         
508         if ((carrier_data = get_carrier_data(rd, carrier_id)) == NULL) {
509                 LM_ERR("could not retrieve carrier data\n");
510                 return -1;
511         }
512         
513         if ((domain_data = get_domain_data_or_add(rd, carrier_data, domain_id)) == NULL) {
514                 LM_ERR("could not retrieve domain data\n");
515                 return -1;
516         }
517
518         LM_INFO("found carrier and domain, now adding failure route\n");
519         return add_failure_route_to_tree(domain_data->failure_tree, scan_prefix, scan_prefix, host, reply_code,
520                         flags, mask, next_domain_id, comment);
521 }
522
523
524 static int fixup_rule_backup(struct route_flags * rf, struct route_rule * rr){
525         struct route_rule_p_list * rl;
526         if(!rr->status && rr->backup){
527                 if((rr->backup->rr = find_rule_by_hash(rf, rr->backup->hash_index)) == NULL){
528                         LM_ERR("didn't find backup route\n");
529                         return -1;
530                 }
531         }
532         rl = rr->backed_up;
533         while(rl){
534                 if((rl->rr = find_rule_by_hash(rf, rl->hash_index)) == NULL){
535                         LM_ERR("didn't find backed up route\n");
536                         return -1;
537                 }
538                 rl = rl->next;
539         }
540         return 0;
541 }
542
543
544 /**
545  * Does the work for rule_fixup recursively.
546  * First, it tries to set a pointer the rules with an existing hash index
547  * at the marching array index. Afterward, remaining rules are populated
548  * with incrementing hash indices.
549  *
550  * @param node the prefix tree node to be fixed up
551  *
552  * @return 0 on success, -1 on failure
553  */
554 static int rule_fixup_recursor(struct dtrie_node_t *node) {
555         struct route_rule * rr;
556         struct route_flags * rf;
557         int i, p_dice, ret = 0;
558
559         for (rf=(struct route_flags *)(node->data); rf!=NULL; rf=rf->next) {
560                 p_dice = 0;
561                 if (rf->rule_list) {
562                         rr = rf->rule_list;
563                         rf->rule_num = 0;
564                         while (rr) {
565                                 rf->rule_num++;
566                                 rf->dice_max += rr->prob * DICE_MAX;
567                                 rr = rr->next;
568                         }
569                         rr = rf->rule_list;
570                         while (rr) {
571                                 rr->dice_to = (rr->prob * DICE_MAX) + p_dice;
572                                 p_dice = rr->dice_to;
573                                 rr = rr->next;
574                         }
575                         
576                         if (rf->rule_num != rf->max_targets) {
577                                 LM_ERR("number of rules(%i) differs from max_targets(%i), maybe your config is wrong?\n", rf->rule_num, rf->max_targets);
578                                 return -1;
579                         }
580                         if(rf->rules) {
581                                 shm_free(rf->rules);
582                                 rf->rules = NULL;
583                         }
584                         if ((rf->rules = shm_malloc(sizeof(struct route_rule *) * rf->rule_num)) == NULL) {
585                                 SHM_MEM_ERROR;
586                                 return -1;
587                         }
588                         memset(rf->rules, 0, sizeof(struct route_rule *) * rf->rule_num);
589                         for (rr = rf->rule_list; rr; rr = rr->next) {
590                                 if (rr->hash_index) {
591                                         if (rr->hash_index > rf->rule_num) {
592                                                 LM_ERR("too large hash index %i, max is %i\n", rr->hash_index, rf->rule_num);
593                                                 shm_free(rf->rules);
594                                                 return -1;
595                                         }
596                                         if (rf->rules[rr->hash_index - 1]) {
597                                                 LM_ERR("duplicate hash index %i\n", rr->hash_index);
598                                                 shm_free(rf->rules);
599                                                 return -1;
600                                         }
601                                         rf->rules[rr->hash_index - 1] = rr;
602                                         LM_INFO("rule with host %.*s hash has hashindex %i.\n", rr->host.len, rr->host.s, rr->hash_index);
603                                 }
604                         }
605                         
606                         rr = rf->rule_list;
607                         i=0;
608                         while (rr && i < rf->rule_num) {
609                                 if (!rr->hash_index) {
610                                         if (rf->rules[i]) {
611                                                 i++;
612                                         } else {
613                                                 rf->rules[i] = rr;
614                                                 rr->hash_index = i + 1;
615                                                 LM_INFO("hashless rule with host %.*s hash, hash_index %i\n", rr->host.len, rr->host.s, i+1);
616                                                 rr = rr->next;
617                                         }
618                                 } else {
619                                         rr = rr->next;
620                                 }
621                         }
622                         if (rr) {
623                                 LM_ERR("Could not populate rules: rr: %p\n", rr);
624                                 return -1;
625                         }
626                         for(i=0; i<rf->rule_num; i++){
627                                 ret += fixup_rule_backup(rf, rf->rules[i]);
628                         }
629                 }
630         }
631
632         for (i=0; i<cr_match_mode; i++) {
633                 if (node->child[i]) {
634                         ret += rule_fixup_recursor(node->child[i]);
635                 }
636         }
637
638         return ret;
639 }
640
641
642 /**
643  * Fixes the route rules by creating an array for accessing
644  * route rules by hash index directly
645  *
646  * @param rd route data to be fixed
647  *
648  * @return 0 on success, -1 on failure
649  */
650 int rule_fixup(struct route_data_t * rd) {
651         int i,j;
652         for (i=0; i<rd->carrier_num; i++) {
653                 for (j=0; j<rd->carriers[i]->domain_num; j++) {
654                         if (rd->carriers[i]->domains[j] && rd->carriers[i]->domains[j]->tree) {
655                                 LM_INFO("fixing tree %.*s\n", rd->carriers[i]->domains[j]->name->len, rd->carriers[i]->domains[j]->name->s);
656                                 if (rule_fixup_recursor(rd->carriers[i]->domains[j]->tree) < 0) {
657                                         return -1;
658                                 }
659                         } else {
660                                 LM_NOTICE("empty tree at [%i][%i]\n", i, j);
661                         }
662                 }
663         }
664         return 0;
665 }