1 /*
2 * $Id: hash_table.cpp 1713 2010-03-30 14:11:14Z rco $
3 *
4 * Copyright (C) 2007 Raphael Coeffic
5 *
6 * This file is part of SEMS, a free SIP media server.
7 *
8 * SEMS 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. This program is released under
12 * the GPL with the additional exemption that compiling, linking,
13 * and/or using OpenSSL is allowed.
14 *
15 * For a license to use the SEMS software under conditions
16 * other than those described here, or to purchase support for this
17 * software, please contact iptel.org by e-mail at the following addresses:
18 * info@iptel.org
19 *
20 * SEMS is distributed in the hope that it will be useful,
21 * but WITHOUT ANY WARRANTY; without even the implied warranty of
22 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
23 * GNU General Public License for more details.
24 *
25 * You should have received a copy of the GNU General Public License
26 * along with this program; if not, write to the Free Software
27 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
28 */
29
30
31 #include "trans_table.h"
32 #include "sip_parser.h"
33 #include "parse_header.h"
34 #include "parse_cseq.h"
35 #include "parse_via.h"
36 #include "parse_from_to.h"
37 #include "parse_100rel.h"
38 #include "sip_trans.h"
39 #include "hash.h"
40
41 #include "log.h"
42
43 #include <assert.h>
44
45 //
46 // Global transaction table
47 //
48
49 hash_table<trans_bucket> _trans_table(H_TABLE_ENTRIES);
50
trans_bucket(unsigned long id)51 trans_bucket::trans_bucket(unsigned long id)
52 : ht_bucket<sip_trans>::ht_bucket(id)
53 {
54 }
55
~trans_bucket()56 trans_bucket::~trans_bucket()
57 {
58 }
59
60 // return true if equal
compare_branch(sip_trans * t,sip_msg * msg,const char * branch,unsigned int branch_len)61 static inline bool compare_branch(sip_trans* t, sip_msg* msg,
62 const char* branch, unsigned int branch_len)
63 {
64 if(t->msg->via_p1->branch.len != branch_len + MAGIC_BRANCH_LEN)
65 return false;
66
67 if(t->msg->via_p1->host.len !=
68 msg->via_p1->host.len)
69 return false;
70
71 if(t->msg->via_p1->port.len !=
72 msg->via_p1->port.len)
73 return false;
74
75 if(memcmp(branch,
76 t->msg->via_p1->branch.s+MAGIC_BRANCH_LEN,branch_len))
77 return false;
78
79 if(memcmp(t->msg->via_p1->host.s,
80 msg->via_p1->host.s,msg->via_p1->host.len))
81 return false;
82
83 if(memcmp(t->msg->via_p1->port.s,
84 msg->via_p1->port.s,msg->via_p1->port.len))
85 return false;
86
87 return true;
88 }
89
90
match_request(sip_msg * msg,unsigned int ttype)91 sip_trans* trans_bucket::match_request(sip_msg* msg, unsigned int ttype)
92 {
93 // assert(msg && msg->cseq && msg->callid);
94 // sip_cseq* cseq = dynamic_cast<sip_cseq*>(msg->cseq->p);
95 // assert(cseq);
96
97 DBG("Matching %.*s request\n",
98 msg->u.request->method_str.len,
99 msg->u.request->method_str.s);
100
101 //this should have been checked before
102 assert(msg->via_p1);
103
104 if(elmts.empty())
105 return NULL;
106
107 bool do_3261_match = false;
108 sip_trans* t = NULL;
109
110 // Try first RFC 3261 matching
111 if(msg->via_p1->branch.len > MAGIC_BRANCH_LEN){
112
113 do_3261_match = !memcmp(msg->via_p1->branch.s,
114 MAGIC_BRANCH_COOKIE,
115 MAGIC_BRANCH_LEN);
116 }
117
118 DBG("do_3261_match = %i\n",do_3261_match);
119 if(do_3261_match){
120
121 const char* branch = msg->via_p1->branch.s + MAGIC_BRANCH_LEN;
122 int len = msg->via_p1->branch.len - MAGIC_BRANCH_LEN;
123
124 trans_list::iterator it = elmts.begin();
125 for(;it!=elmts.end();++it) {
126
127 if( ((*it)->msg->type != SIP_REQUEST) ||
128 ((*it)->type != ttype)){
129 continue;
130 }
131
132 if(msg->u.request->method != (*it)->msg->u.request->method) {
133
134 // ACK is the only request that should match an existing
135 // transaction without being a re-transmission
136 if( ((*it)->msg->u.request->method == sip_request::INVITE)
137 && (msg->u.request->method == sip_request::ACK)) {
138
139 // match non-200 ACK first
140 if(compare_branch(*it,msg,branch,(unsigned int)len)) {
141 t = *it;
142 break;
143 }
144
145 // branches do not match,
146 // try to match a 200-ACK
147 if((t = match_200_ack(*it,msg)) != NULL)
148 break;
149 }
150
151 continue;
152 }
153
154 if(!compare_branch(*it,msg,branch,(unsigned int)len))
155 continue;
156
157 // found matching transaction
158 t = *it;
159 break;
160 }
161 }
162 else {
163
164 // Pre-3261 matching
165
166 sip_from_to* from = dynamic_cast<sip_from_to*>(msg->from->p);
167 sip_from_to* to = dynamic_cast<sip_from_to*>(msg->to->p);
168 sip_cseq* cseq = dynamic_cast<sip_cseq*>(msg->cseq->p);
169
170 assert(from && to && cseq);
171
172 trans_list::iterator it = elmts.begin();
173 for(;it!=elmts.end();++it) {
174
175
176 //Request matching:
177 // Request-URI
178 // From-tag
179 // Call-ID
180 // Cseq
181 // top Via
182 // To-tag
183
184 //ACK matching:
185 // Request-URI
186 // From-tag
187 // Call-ID
188 // Cseq (number only)
189 // top Via
190 // + To-tag of reply
191
192 if( ((*it)->msg->type != SIP_REQUEST) ||
193 ((*it)->type != ttype)){
194 continue;
195 }
196
197 if( (msg->u.request->method != (*it)->msg->u.request->method) &&
198 ( (msg->u.request->method != sip_request::ACK) ||
199 ((*it)->msg->u.request->method != sip_request::INVITE) ) )
200 continue;
201
202 sip_from_to* it_from = dynamic_cast<sip_from_to*>((*it)->msg->from->p);
203 if(from->tag.len != it_from->tag.len)
204 continue;
205
206 sip_cseq* it_cseq = dynamic_cast<sip_cseq*>((*it)->msg->cseq->p);
207 if(cseq->num_str.len != it_cseq->num_str.len)
208 continue;
209
210 if(memcmp(from->tag.s,it_from->tag.s,from->tag.len))
211 continue;
212
213 if(memcmp(cseq->num_str.s,it_cseq->num_str.s,cseq->num_str.len))
214 continue;
215
216
217 if(msg->u.request->method == sip_request::ACK){
218
219 // ACKs must include To-tag from previous reply
220 if(to->tag.len != (*it)->to_tag.len)
221 continue;
222
223 if(memcmp(to->tag.s,(*it)->to_tag.s,to->tag.len))
224 continue;
225
226 if((*it)->reply_status < 300){
227
228 // 2xx ACK matching
229
230 // TODO: additional work for dialog matching???
231 // R-URI should match reply Contact ...
232 // Anyway, we don't keep the contact from reply.
233 t = *it;
234 break;
235 }
236 }
237 else {
238 // non-ACK
239 sip_from_to* it_to = dynamic_cast<sip_from_to*>((*it)->msg->to->p);
240 if(to->tag.len != it_to->tag.len)
241 continue;
242
243 if(memcmp(to->tag.s,it_to->tag.s,to->tag.len))
244 continue;
245 }
246
247 // non-ACK and non-2xx ACK matching
248
249 if((*it)->msg->u.request->ruri_str.len !=
250 msg->u.request->ruri_str.len )
251 continue;
252
253 if(memcmp(msg->u.request->ruri_str.s,
254 (*it)->msg->u.request->ruri_str.s,
255 msg->u.request->ruri_str.len))
256 continue;
257
258 //TODO: missing top-Via matching
259
260 // found matching transaction
261 t = *it;
262 break;
263 }
264 }
265
266 return t;
267 }
268
match_reply(sip_msg * msg)269 sip_trans* trans_bucket::match_reply(sip_msg* msg)
270 {
271
272 if(elmts.empty())
273 return NULL;
274
275 assert(msg->via_p1);
276 if(msg->via_p1->branch.len <= MAGIC_BRANCH_LEN){
277 // this cannot match...
278 return NULL;
279 }
280
281 sip_trans* t = NULL;
282
283 const char* branch = msg->via_p1->branch.s + MAGIC_BRANCH_LEN;
284 int len = msg->via_p1->branch.len - MAGIC_BRANCH_LEN;
285
286 assert(get_cseq(msg));
287
288 trans_list::iterator it = elmts.begin();
289 for(;it!=elmts.end();++it) {
290
291 if((*it)->type != TT_UAC){
292 continue;
293 }
294
295 if((*it)->msg->via_p1->branch.len != msg->via_p1->branch.len)
296 continue;
297
298 if(get_cseq((*it)->msg)->num_str.len != get_cseq(msg)->num_str.len)
299 continue;
300
301 if(get_cseq((*it)->msg)->method_str.len != get_cseq(msg)->method_str.len)
302 continue;
303
304 if(memcmp((*it)->msg->via_p1->branch.s+MAGIC_BRANCH_LEN,
305 branch,len))
306 continue;
307
308 if(memcmp(get_cseq((*it)->msg)->num_str.s,get_cseq(msg)->num_str.s,
309 get_cseq(msg)->num_str.len))
310 continue;
311
312 if(memcmp(get_cseq((*it)->msg)->method_str.s,get_cseq(msg)->method_str.s,
313 get_cseq(msg)->method_str.len))
314 continue;
315
316 // found matching transaction
317 t = *it;
318 break;
319 }
320
321 return t;
322 }
323
match_200_ack(sip_trans * t,sip_msg * msg)324 sip_trans* trans_bucket::match_200_ack(sip_trans* t, sip_msg* msg)
325 {
326 sip_from_to* from = dynamic_cast<sip_from_to*>(msg->from->p);
327 sip_from_to* to = dynamic_cast<sip_from_to*>(msg->to->p);
328 sip_cseq* cseq = dynamic_cast<sip_cseq*>(msg->cseq->p);
329
330 assert(from && to && cseq);
331
332 sip_from_to* t_from = dynamic_cast<sip_from_to*>(t->msg->from->p);
333 if(from->tag.len != t_from->tag.len)
334 return NULL;
335
336 sip_cseq* t_cseq = dynamic_cast<sip_cseq*>(t->msg->cseq->p);
337 if(cseq->num != t_cseq->num)
338 return NULL;
339
340 if(msg->callid->value.len != t->msg->callid->value.len)
341 return NULL;
342
343 if(to->tag.len != t->to_tag.len)
344 return NULL;
345
346 if(memcmp(from->tag.s,t_from->tag.s,from->tag.len))
347 return NULL;
348
349 if(memcmp(msg->callid->value.s,t->msg->callid->value.s,
350 msg->callid->value.len))
351 return NULL;
352
353 if(memcmp(to->tag.s,t->to_tag.s,to->tag.len))
354 return NULL;
355
356 return t;
357 }
358
match_1xx_prack(sip_msg * msg)359 sip_trans* trans_bucket::match_1xx_prack(sip_msg* msg)
360 {
361 DBG("Matching %.*s request\n",
362 msg->u.request->method_str.len,
363 msg->u.request->method_str.s);
364
365 if(elmts.empty())
366 return NULL;
367
368 trans_list::iterator it = elmts.begin();
369 for(;it!=elmts.end();++it) {
370
371 if( (*it)->msg->type != SIP_REQUEST ){
372 continue;
373 }
374 sip_trans* t = *it;
375
376 /* first, check quickly if lenghts match (From tag, To tag, Call-ID) */
377
378 sip_from_to* from = dynamic_cast<sip_from_to*>(msg->from->p);
379 sip_from_to* t_from = dynamic_cast<sip_from_to*>(t->msg->from->p);
380 if(from->tag.len != t_from->tag.len)
381 continue;
382
383 sip_from_to* to = dynamic_cast<sip_from_to*>(msg->to->p);
384 if(to->tag.len != t->to_tag.len)
385 continue;
386
387 if(msg->callid->value.len != t->msg->callid->value.len)
388 continue;
389
390 sip_rack *rack = dynamic_cast<sip_rack *>(msg->rack->p);
391 sip_cseq* t_cseq = dynamic_cast<sip_cseq*>(t->msg->cseq->p);
392 if (rack->cseq != t_cseq->num)
393 continue;
394
395 if (rack->rseq != t->last_rseq)
396 continue;
397
398 if (rack->method != t->msg->u.request->method)
399 continue;
400
401 /* numbers fit, try content */
402 if(memcmp(from->tag.s,t_from->tag.s,from->tag.len))
403 continue;
404
405 if(memcmp(msg->callid->value.s,t->msg->callid->value.s,
406 msg->callid->value.len))
407 continue;
408
409 if(memcmp(to->tag.s,t->to_tag.s,to->tag.len))
410 continue;
411
412 return t;
413 }
414
415 return NULL;
416 }
417
find_uac_trans(const cstring & dialog_id,unsigned int inv_cseq)418 sip_trans* trans_bucket::find_uac_trans(const cstring& dialog_id,
419 unsigned int inv_cseq)
420 {
421 DBG("Matching dialog_id = '%.*s'\n",
422 dialog_id.len, dialog_id.s);
423
424 if(elmts.empty())
425 return NULL;
426
427 trans_list::reverse_iterator it = elmts.rbegin();
428 for(;it!=elmts.rend();++it) {
429
430 sip_trans* t = *it;
431 if( t->type != TT_UAC ||
432 t->msg->type != SIP_REQUEST ){
433 continue;
434 }
435 sip_cseq* t_cseq = dynamic_cast<sip_cseq*>(t->msg->cseq->p);
436 if(t->dialog_id == dialog_id &&
437 t_cseq && t_cseq->num == inv_cseq &&
438 t->state != TS_ABANDONED)
439 return t;
440 }
441
442 return NULL;
443 }
444
add_trans(sip_msg * msg,unsigned int ttype)445 sip_trans* trans_bucket::add_trans(sip_msg* msg, unsigned int ttype)
446 {
447 sip_trans* t = new sip_trans();
448
449 t->msg = msg;
450 t->type = ttype;
451
452 t->reply_status = 0;
453
454 assert(msg->type == SIP_REQUEST);
455 if(msg->u.request->method == sip_request::INVITE){
456
457 if(t->type == TT_UAS)
458 t->state = TS_PROCEEDING;
459 else
460 t->state = TS_CALLING;
461 }
462 else {
463 t->state = TS_TRYING;
464 }
465
466 elmts.push_back(t);
467
468 return t;
469 }
470
append(sip_trans * t)471 void trans_bucket::append(sip_trans* t)
472 {
473 elmts.push_back(t);
474 }
475
hash(const cstring & ci,const cstring & cs)476 unsigned int hash(const cstring& ci, const cstring& cs)
477 {
478 unsigned int h=0;
479
480 h = hashlittle(ci.s,ci.len,h);
481 h = hashlittle(cs.s,cs.len,h);
482
483 return h;
484 }
485
486 char _tag_lookup[] = {
487 'a','b','c','d','e','f','g','h',
488 'i','j','k','l','m','n','o','p',
489 'q','r','s','t','u','v','w','x',
490 'y','z','A','B','C','D','E','F',
491 'G','H','I','J','K','L','M','N',
492 'O','P','Q','R','S','T','U','V',
493 'W','X','Y','Z','0','1','2','3',
494 '4','5','6','7','8','9','.','~'
495 };
496
compute_tag(char * tag,unsigned int hl,unsigned int hh)497 inline void compute_tag(char* tag, unsigned int hl, unsigned int hh)
498 {
499 hl += hh >> 16;
500 hh &= 0xFFFF;
501
502 tag[0] = _tag_lookup[hl&0x3F];
503 tag[1] = _tag_lookup[(hl >> 6)&0x3F];
504 tag[2] = _tag_lookup[(hl >> 12)&0x3F];
505 tag[3] = _tag_lookup[(hl >> 18)&0x3F];
506 tag[4] = _tag_lookup[(hl >> 24)&0x3F];
507 tag[5] = _tag_lookup[(hl >> 30)&((hh << 2) & 0x3F)];
508 tag[6] = _tag_lookup[(hh >> 4)&0x3F];
509 tag[7] = _tag_lookup[(hh >> 10)&0x3F];
510 }
511
512 static atomic_int __branch_cnt;
513
compute_sl_to_tag(char * to_tag,const sip_msg * msg)514 void compute_sl_to_tag(char* to_tag/*[8]*/, const sip_msg* msg)
515 {
516 unsigned int hl = __branch_cnt.inc();
517 unsigned int hh = __branch_cnt.inc();
518
519 assert(msg->type == SIP_REQUEST);
520 assert(msg->u.request);
521
522 hl = hashlittle(msg->u.request->method_str.s,
523 msg->u.request->method_str.len,hl);
524
525 hl = hashlittle(msg->u.request->ruri_str.s,
526 msg->u.request->ruri_str.len,hl);
527
528 if(msg->callid){
529 hh = hashlittle(msg->callid->value.s,
530 msg->callid->value.len,hh);
531 }
532
533 if(msg->from){
534 hh = hashlittle(msg->from->value.s,
535 msg->from->value.len,hh);
536 }
537
538 if(msg->cseq){
539 hh = hashlittle(msg->cseq->value.s,
540 msg->cseq->value.len,hh);
541 }
542
543 compute_tag(to_tag,hl,hh);
544 }
545
compute_branch(char * branch,const cstring & callid,const cstring & cseq)546 void compute_branch(char* branch/*[8]*/, const cstring& callid, const cstring& cseq)
547 {
548 unsigned int hl=0;
549 unsigned int hh=0;
550
551 hh = __branch_cnt.inc();
552 hl = __branch_cnt.inc();
553
554 hl = hashlittle(callid.s,callid.len,hl);
555 hh = hashlittle(cseq.s,cseq.len,hh);
556
557 compute_tag(branch,hl,hh);
558 }
559
get_trans_bucket(const cstring & callid,const cstring & cseq_num)560 trans_bucket* get_trans_bucket(const cstring& callid, const cstring& cseq_num)
561 {
562 return _trans_table[hash(callid,cseq_num)];
563 }
564
get_trans_bucket(unsigned int h)565 trans_bucket* get_trans_bucket(unsigned int h)
566 {
567 return _trans_table[h];
568 }
569
dumps_transactions()570 void dumps_transactions()
571 {
572 _trans_table.dump();
573 }
574
575
576 /** EMACS **
577 * Local variables:
578 * mode: c++
579 * c-basic-offset: 4
580 * End:
581 */
582