208c2308b952b7685917e1a36748ed29eb47d950
[asterisk/asterisk.git] / main / pbx.c
1 /*
2  * Asterisk -- An open source telephony toolkit.
3  *
4  * Copyright (C) 1999 - 2008, Digium, Inc.
5  *
6  * Mark Spencer <markster@digium.com>
7  *
8  * See http://www.asterisk.org for more information about
9  * the Asterisk project. Please do not directly contact
10  * any of the maintainers of this project for assistance;
11  * the project provides a web site, mailing lists and IRC
12  * channels for your use.
13  *
14  * This program is free software, distributed under the terms of
15  * the GNU General Public License Version 2. See the LICENSE file
16  * at the top of the source tree.
17  */
18
19 /*! \file
20  *
21  * \brief Core PBX routines.
22  *
23  * \author Mark Spencer <markster@digium.com>
24  */
25
26 /*** MODULEINFO
27         <support_level>core</support_level>
28  ***/
29
30 #include "asterisk.h"
31
32 #include "asterisk/_private.h"
33 #include "asterisk/paths.h"     /* use ast_config_AST_SYSTEM_NAME */
34 #include <ctype.h>
35 #include <time.h>
36 #include <sys/time.h>
37 #if defined(HAVE_SYSINFO)
38 #include <sys/sysinfo.h>
39 #endif
40 #if defined(SOLARIS)
41 #include <sys/loadavg.h>
42 #endif
43
44 #include "asterisk/lock.h"
45 #include "asterisk/cli.h"
46 #include "asterisk/pbx.h"
47 #include "asterisk/channel.h"
48 #include "asterisk/file.h"
49 #include "asterisk/callerid.h"
50 #include "asterisk/cdr.h"
51 #include "asterisk/config.h"
52 #include "asterisk/term.h"
53 #include "asterisk/time.h"
54 #include "asterisk/manager.h"
55 #include "asterisk/ast_expr.h"
56 #include "asterisk/linkedlists.h"
57 #define SAY_STUBS       /* generate declarations and stubs for say methods */
58 #include "asterisk/say.h"
59 #include "asterisk/utils.h"
60 #include "asterisk/causes.h"
61 #include "asterisk/musiconhold.h"
62 #include "asterisk/app.h"
63 #include "asterisk/devicestate.h"
64 #include "asterisk/presencestate.h"
65 #include "asterisk/hashtab.h"
66 #include "asterisk/module.h"
67 #include "asterisk/indications.h"
68 #include "asterisk/taskprocessor.h"
69 #include "asterisk/xmldoc.h"
70 #include "asterisk/astobj2.h"
71 #include "asterisk/stasis_channels.h"
72 #include "asterisk/dial.h"
73 #include "asterisk/vector.h"
74 #include "pbx_private.h"
75
76 /*!
77  * \note I M P O R T A N T :
78  *
79  *              The speed of extension handling will likely be among the most important
80  * aspects of this PBX.  The switching scheme as it exists right now isn't
81  * terribly bad (it's O(N+M), where N is the # of extensions and M is the avg #
82  * of priorities, but a constant search time here would be great ;-)
83  *
84  * A new algorithm to do searching based on a 'compiled' pattern tree is introduced
85  * here, and shows a fairly flat (constant) search time, even for over
86  * 10000 patterns.
87  *
88  * Also, using a hash table for context/priority name lookup can help prevent
89  * the find_extension routines from absorbing exponential cpu cycles as the number
90  * of contexts/priorities grow. I've previously tested find_extension with red-black trees,
91  * which have O(log2(n)) speed. Right now, I'm using hash tables, which do
92  * searches (ideally) in O(1) time. While these techniques do not yield much
93  * speed in small dialplans, they are worth the trouble in large dialplans.
94  *
95  */
96
97 /*** DOCUMENTATION
98         <function name="EXCEPTION" language="en_US">
99                 <synopsis>
100                         Retrieve the details of the current dialplan exception.
101                 </synopsis>
102                 <syntax>
103                         <parameter name="field" required="true">
104                                 <para>The following fields are available for retrieval:</para>
105                                 <enumlist>
106                                         <enum name="reason">
107                                                 <para>INVALID, ERROR, RESPONSETIMEOUT, ABSOLUTETIMEOUT, or custom
108                                                 value set by the RaiseException() application</para>
109                                         </enum>
110                                         <enum name="context">
111                                                 <para>The context executing when the exception occurred.</para>
112                                         </enum>
113                                         <enum name="exten">
114                                                 <para>The extension executing when the exception occurred.</para>
115                                         </enum>
116                                         <enum name="priority">
117                                                 <para>The numeric priority executing when the exception occurred.</para>
118                                         </enum>
119                                 </enumlist>
120                         </parameter>
121                 </syntax>
122                 <description>
123                         <para>Retrieve the details (specified <replaceable>field</replaceable>) of the current dialplan exception.</para>
124                 </description>
125                 <see-also>
126                         <ref type="application">RaiseException</ref>
127                 </see-also>
128         </function>
129         <function name="TESTTIME" language="en_US">
130                 <synopsis>
131                         Sets a time to be used with the channel to test logical conditions.
132                 </synopsis>
133                 <syntax>
134                         <parameter name="date" required="true" argsep=" ">
135                                 <para>Date in ISO 8601 format</para>
136                         </parameter>
137                         <parameter name="time" required="true" argsep=" ">
138                                 <para>Time in HH:MM:SS format (24-hour time)</para>
139                         </parameter>
140                         <parameter name="zone" required="false">
141                                 <para>Timezone name</para>
142                         </parameter>
143                 </syntax>
144                 <description>
145                         <para>To test dialplan timing conditions at times other than the current time, use
146                         this function to set an alternate date and time.  For example, you may wish to evaluate
147                         whether a location will correctly identify to callers that the area is closed on Christmas
148                         Day, when Christmas would otherwise fall on a day when the office is normally open.</para>
149                 </description>
150                 <see-also>
151                         <ref type="application">GotoIfTime</ref>
152                 </see-also>
153         </function>
154         <manager name="ShowDialPlan" language="en_US">
155                 <synopsis>
156                         Show dialplan contexts and extensions
157                 </synopsis>
158                 <syntax>
159                         <xi:include xpointer="xpointer(/docs/manager[@name='Login']/syntax/parameter[@name='ActionID'])" />
160                         <parameter name="Extension">
161                                 <para>Show a specific extension.</para>
162                         </parameter>
163                         <parameter name="Context">
164                                 <para>Show a specific context.</para>
165                         </parameter>
166                 </syntax>
167                 <description>
168                         <para>Show dialplan contexts and extensions. Be aware that showing the full dialplan
169                         may take a lot of capacity.</para>
170                 </description>
171         </manager>
172         <manager name="ExtensionStateList" language="en_US">
173                 <synopsis>
174                         List the current known extension states.
175                 </synopsis>
176                 <syntax>
177                         <xi:include xpointer="xpointer(/docs/manager[@name='Login']/syntax/parameter[@name='ActionID'])" />
178                 </syntax>
179                 <description>
180                         <para>This will list out all known extension states in a
181                         sequence of <replaceable>ExtensionStatus</replaceable> events.
182                         When finished, a <replaceable>ExtensionStateListComplete</replaceable> event
183                         will be emitted.</para>
184                 </description>
185                 <see-also>
186                         <ref type="manager">ExtensionState</ref>
187                         <ref type="function">HINT</ref>
188                         <ref type="function">EXTENSION_STATE</ref>
189                 </see-also>
190                 <responses>
191                         <list-elements>
192                                 <xi:include xpointer="xpointer(/docs/managerEvent[@name='ExtensionStatus'])" />
193                         </list-elements>
194                         <managerEvent name="ExtensionStateListComplete" language="en_US">
195                                 <managerEventInstance class="EVENT_FLAG_COMMAND">
196                                         <synopsis>
197                                                 Indicates the end of the list the current known extension states.
198                                         </synopsis>
199                                         <syntax>
200                                                 <parameter name="EventList">
201                                                         <para>Conveys the status of the event list.</para>
202                                                 </parameter>
203                                                 <parameter name="ListItems">
204                                                         <para>Conveys the number of statuses reported.</para>
205                                                 </parameter>
206                                         </syntax>
207                                 </managerEventInstance>
208                         </managerEvent>
209                 </responses>
210         </manager>
211  ***/
212
213 #ifdef LOW_MEMORY
214 #define EXT_DATA_SIZE 256
215 #else
216 #define EXT_DATA_SIZE 8192
217 #endif
218
219 #define SWITCH_DATA_LENGTH 256
220
221 #define VAR_NORMAL              1
222 #define VAR_SOFTTRAN    2
223 #define VAR_HARDTRAN    3
224
225 struct ast_context;
226 struct ast_app;
227
228 AST_THREADSTORAGE(switch_data);
229 AST_THREADSTORAGE(extensionstate_buf);
230
231 /*!
232    \brief ast_exten: An extension
233         The dialplan is saved as a linked list with each context
234         having it's own linked list of extensions - one item per
235         priority.
236 */
237 struct ast_exten {
238         char *exten;                    /*!< Clean Extension id */
239         char *name;                     /*!< Extension name (may include '-' eye candy) */
240         int matchcid;                   /*!< Match caller id ? */
241         const char *cidmatch;           /*!< Caller id to match for this extension */
242         const char *cidmatch_display;   /*!< Caller id to match (display version) */
243         int priority;                   /*!< Priority */
244         const char *label;              /*!< Label */
245         struct ast_context *parent;     /*!< The context this extension belongs to  */
246         const char *app;                /*!< Application to execute */
247         struct ast_app *cached_app;     /*!< Cached location of application */
248         void *data;                     /*!< Data to use (arguments) */
249         void (*datad)(void *);          /*!< Data destructor */
250         struct ast_exten *peer;         /*!< Next higher priority with our extension */
251         struct ast_hashtab *peer_table;    /*!< Priorities list in hashtab form -- only on the head of the peer list */
252         struct ast_hashtab *peer_label_table; /*!< labeled priorities in the peers -- only on the head of the peer list */
253         const char *registrar;          /*!< Registrar */
254         struct ast_exten *next;         /*!< Extension with a greater ID */
255         char stuff[0];
256 };
257
258 /*! \brief match_char: forms a syntax tree for quick matching of extension patterns */
259 struct match_char
260 {
261         int is_pattern; /* the pattern started with '_' */
262         int deleted;    /* if this is set, then... don't return it */
263         int specificity; /* simply the strlen of x, or 10 for X, 9 for Z, and 8 for N; and '.' and '!' will add 11 ? */
264         struct match_char *alt_char;
265         struct match_char *next_char;
266         struct ast_exten *exten; /* attached to last char of a pattern for exten */
267         char x[1];       /* the pattern itself-- matches a single char */
268 };
269
270 struct scoreboard  /* make sure all fields are 0 before calling new_find_extension */
271 {
272         int total_specificity;
273         int total_length;
274         char last_char;   /* set to ! or . if they are the end of the pattern */
275         int canmatch;     /* if the string to match was just too short */
276         struct match_char *node;
277         struct ast_exten *canmatch_exten;
278         struct ast_exten *exten;
279 };
280
281 /*! \brief ast_context: An extension context - must remain in sync with fake_context */
282 struct ast_context {
283         ast_rwlock_t lock;                      /*!< A lock to prevent multiple threads from clobbering the context */
284         struct ast_exten *root;                 /*!< The root of the list of extensions */
285         struct ast_hashtab *root_table;            /*!< For exact matches on the extensions in the pattern tree, and for traversals of the pattern_tree  */
286         struct match_char *pattern_tree;        /*!< A tree to speed up extension pattern matching */
287         struct ast_context *next;               /*!< Link them together */
288         struct ast_includes includes;           /*!< Include other contexts */
289         struct ast_ignorepats ignorepats;       /*!< Patterns for which to continue playing dialtone */
290         struct ast_sws alts;                    /*!< Alternative switches */
291         char *registrar;                        /*!< Registrar -- make sure you malloc this, as the registrar may have to survive module unloads */
292         int refcount;                   /*!< each module that would have created this context should inc/dec this as appropriate */
293         int autohints;                  /*!< Whether autohints support is enabled or not */
294         ast_mutex_t macrolock;                  /*!< A lock to implement "exclusive" macros - held whilst a call is executing in the macro */
295         char name[0];                           /*!< Name of the context */
296 };
297
298 /*! \brief ast_state_cb: An extension state notify register item */
299 struct ast_state_cb {
300         /*! Watcher ID returned when registered. */
301         int id;
302         /*! Arbitrary data passed for callbacks. */
303         void *data;
304         /*! Flag if this callback is an extended callback containing detailed device status */
305         int extended;
306         /*! Callback when state changes. */
307         ast_state_cb_type change_cb;
308         /*! Callback when destroyed so any resources given by the registerer can be freed. */
309         ast_state_cb_destroy_type destroy_cb;
310         /*! \note Only used by ast_merge_contexts_and_delete */
311         AST_LIST_ENTRY(ast_state_cb) entry;
312 };
313
314 /*!
315  * \brief Structure for dial plan hints
316  *
317  * \note Hints are pointers from an extension in the dialplan to
318  * one or more devices (tech/name)
319  *
320  * See \ref AstExtState
321  */
322 struct ast_hint {
323         /*!
324          * \brief Hint extension
325          *
326          * \note
327          * Will never be NULL while the hint is in the hints container.
328          */
329         struct ast_exten *exten;
330         struct ao2_container *callbacks; /*!< Device state callback container for this extension */
331
332         /*! Dev state variables */
333         int laststate;                  /*!< Last known device state */
334
335         /*! Presence state variables */
336         int last_presence_state;     /*!< Last known presence state */
337         char *last_presence_subtype; /*!< Last known presence subtype string */
338         char *last_presence_message; /*!< Last known presence message string */
339
340         char context_name[AST_MAX_CONTEXT];/*!< Context of destroyed hint extension. */
341         char exten_name[AST_MAX_EXTENSION];/*!< Extension of destroyed hint extension. */
342
343         AST_VECTOR(, char *) devices; /*!< Devices associated with the hint */
344 };
345
346 STASIS_MESSAGE_TYPE_DEFN_LOCAL(hint_change_message_type);
347
348 #define HINTDEVICE_DATA_LENGTH 16
349 AST_THREADSTORAGE(hintdevice_data);
350
351 /* --- Hash tables of various objects --------*/
352 #ifdef LOW_MEMORY
353 #define HASH_EXTENHINT_SIZE 17
354 #else
355 #define HASH_EXTENHINT_SIZE 563
356 #endif
357
358
359 /*! \brief Container for hint devices */
360 static struct ao2_container *hintdevices;
361
362 /*!
363  * \brief Structure for dial plan hint devices
364  * \note hintdevice is one device pointing to a hint.
365  */
366 struct ast_hintdevice {
367         /*!
368          * \brief Hint this hintdevice belongs to.
369          * \note Holds a reference to the hint object.
370          */
371         struct ast_hint *hint;
372         /*! Name of the hint device. */
373         char hintdevice[1];
374 };
375
376 /*! \brief Container for autohint contexts */
377 static struct ao2_container *autohints;
378
379 /*!
380  * \brief Structure for dial plan autohints
381  */
382 struct ast_autohint {
383         /*! \brief Name of the registrar */
384         char *registrar;
385         /*! \brief Name of the context */
386         char context[1];
387 };
388
389 /*!
390  * \note Using the device for hash
391  */
392 static int hintdevice_hash_cb(const void *obj, const int flags)
393 {
394         const struct ast_hintdevice *ext;
395         const char *key;
396
397         switch (flags & OBJ_SEARCH_MASK) {
398         case OBJ_SEARCH_KEY:
399                 key = obj;
400                 break;
401         case OBJ_SEARCH_OBJECT:
402                 ext = obj;
403                 key = ext->hintdevice;
404                 break;
405         default:
406                 ast_assert(0);
407                 return 0;
408         }
409
410         return ast_str_case_hash(key);
411 }
412
413 /*!
414  * \note Devices on hints are not unique so no CMP_STOP is returned
415  * Dont use ao2_find against hintdevices container cause there always
416  * could be more than one result.
417  */
418 static int hintdevice_cmp_multiple(void *obj, void *arg, int flags)
419 {
420         struct ast_hintdevice *left = obj;
421         struct ast_hintdevice *right = arg;
422         const char *right_key = arg;
423         int cmp;
424
425         switch (flags & OBJ_SEARCH_MASK) {
426         case OBJ_SEARCH_OBJECT:
427                 right_key = right->hintdevice;
428                 /* Fall through */
429         case OBJ_SEARCH_KEY:
430                 cmp = strcasecmp(left->hintdevice, right_key);
431                 break;
432         case OBJ_SEARCH_PARTIAL_KEY:
433                 /*
434                 * We could also use a partial key struct containing a length
435                 * so strlen() does not get called for every comparison instead.
436                 */
437                 cmp = strncmp(left->hintdevice, right_key, strlen(right_key));
438                 break;
439         default:
440                 ast_assert(0);
441                 cmp = 0;
442                 break;
443         }
444         return cmp ? 0 : CMP_MATCH;
445 }
446
447 /*!
448  * \note Using the context name for hash
449  */
450 static int autohint_hash_cb(const void *obj, const int flags)
451 {
452         const struct ast_autohint *autohint;
453         const char *key;
454
455         switch (flags & OBJ_SEARCH_MASK) {
456         case OBJ_SEARCH_KEY:
457                 key = obj;
458                 break;
459         case OBJ_SEARCH_OBJECT:
460                 autohint = obj;
461                 key = autohint->context;
462                 break;
463         default:
464                 ast_assert(0);
465                 return 0;
466         }
467
468         return ast_str_case_hash(key);
469 }
470
471 static int autohint_cmp(void *obj, void *arg, int flags)
472 {
473         struct ast_autohint *left = obj;
474         struct ast_autohint *right = arg;
475         const char *right_key = arg;
476         int cmp;
477
478         switch (flags & OBJ_SEARCH_MASK) {
479         case OBJ_SEARCH_OBJECT:
480                 right_key = right->context;
481                 /* Fall through */
482         case OBJ_SEARCH_KEY:
483                 cmp = strcasecmp(left->context, right_key);
484                 break;
485         case OBJ_SEARCH_PARTIAL_KEY:
486                 /*
487                 * We could also use a partial key struct containing a length
488                 * so strlen() does not get called for every comparison instead.
489                 */
490                 cmp = strncmp(left->context, right_key, strlen(right_key));
491                 break;
492         default:
493                 ast_assert(0);
494                 cmp = 0;
495                 break;
496         }
497         return cmp ? 0 : CMP_MATCH | CMP_STOP;
498 }
499
500 /*! \internal \brief \c ao2_callback function to remove hintdevices */
501 static int hintdevice_remove_cb(void *obj, void *arg, void *data, int flags)
502 {
503         struct ast_hintdevice *candidate = obj;
504         char *device = arg;
505         struct ast_hint *hint = data;
506
507         if (!strcasecmp(candidate->hintdevice, device)
508                 && candidate->hint == hint) {
509                 return CMP_MATCH;
510         }
511         return 0;
512 }
513
514 static int remove_hintdevice(struct ast_hint *hint)
515 {
516         while (AST_VECTOR_SIZE(&hint->devices) > 0) {
517                 char *device = AST_VECTOR_GET(&hint->devices, 0);
518
519                 ao2_t_callback_data(hintdevices, OBJ_SEARCH_KEY | OBJ_UNLINK | OBJ_NODATA,
520                         hintdevice_remove_cb, device, hint, "Remove device from container");
521                 AST_VECTOR_REMOVE_UNORDERED(&hint->devices, 0);
522                 ast_free(device);
523         }
524
525         return 0;
526 }
527
528 static char *parse_hint_device(struct ast_str *hint_args);
529 /*!
530  * \internal
531  * \brief Destroy the given hintdevice object.
532  *
533  * \param obj Hint device to destroy.
534  *
535  * \return Nothing
536  */
537 static void hintdevice_destroy(void *obj)
538 {
539         struct ast_hintdevice *doomed = obj;
540
541         if (doomed->hint) {
542                 ao2_ref(doomed->hint, -1);
543                 doomed->hint = NULL;
544         }
545 }
546
547 /*! \brief add hintdevice structure and link it into the container.
548  */
549 static int add_hintdevice(struct ast_hint *hint, const char *devicelist)
550 {
551         struct ast_str *str;
552         char *parse;
553         char *cur;
554         struct ast_hintdevice *device;
555         int devicelength;
556
557         if (!hint || !devicelist) {
558                 /* Trying to add garbage? Don't bother. */
559                 return 0;
560         }
561         if (!(str = ast_str_thread_get(&hintdevice_data, 16))) {
562                 return -1;
563         }
564         ast_str_set(&str, 0, "%s", devicelist);
565         parse = ast_str_buffer(str);
566
567         /* Spit on '&' and ',' to handle presence hints as well */
568         while ((cur = strsep(&parse, "&,"))) {
569                 char *device_name;
570
571                 devicelength = strlen(cur);
572                 if (!devicelength) {
573                         continue;
574                 }
575
576                 device_name = ast_strdup(cur);
577                 if (!device_name) {
578                         return -1;
579                 }
580
581                 device = ao2_t_alloc(sizeof(*device) + devicelength, hintdevice_destroy,
582                         "allocating a hintdevice structure");
583                 if (!device) {
584                         ast_free(device_name);
585                         return -1;
586                 }
587                 strcpy(device->hintdevice, cur);
588                 ao2_ref(hint, +1);
589                 device->hint = hint;
590                 if (AST_VECTOR_APPEND(&hint->devices, device_name)) {
591                         ast_free(device_name);
592                         ao2_ref(device, -1);
593                         return -1;
594                 }
595                 ao2_t_link(hintdevices, device, "Linking device into hintdevice container.");
596                 ao2_t_ref(device, -1, "hintdevice is linked so we can unref");
597         }
598
599         return 0;
600 }
601
602
603 static const struct cfextension_states {
604         int extension_state;
605         const char * const text;
606 } extension_states[] = {
607         { AST_EXTENSION_NOT_INUSE,                     "Idle" },
608         { AST_EXTENSION_INUSE,                         "InUse" },
609         { AST_EXTENSION_BUSY,                          "Busy" },
610         { AST_EXTENSION_UNAVAILABLE,                   "Unavailable" },
611         { AST_EXTENSION_RINGING,                       "Ringing" },
612         { AST_EXTENSION_INUSE | AST_EXTENSION_RINGING, "InUse&Ringing" },
613         { AST_EXTENSION_ONHOLD,                        "Hold" },
614         { AST_EXTENSION_INUSE | AST_EXTENSION_ONHOLD,  "InUse&Hold" }
615 };
616
617 struct pbx_exception {
618         AST_DECLARE_STRING_FIELDS(
619                 AST_STRING_FIELD(context);      /*!< Context associated with this exception */
620                 AST_STRING_FIELD(exten);        /*!< Exten associated with this exception */
621                 AST_STRING_FIELD(reason);               /*!< The exception reason */
622         );
623
624         int priority;                           /*!< Priority associated with this exception */
625 };
626
627 static int matchcid(const char *cidpattern, const char *callerid);
628 #ifdef NEED_DEBUG
629 static void log_match_char_tree(struct match_char *node, char *prefix); /* for use anywhere */
630 #endif
631 static void new_find_extension(const char *str, struct scoreboard *score,
632                 struct match_char *tree, int length, int spec, const char *callerid,
633                 const char *label, enum ext_match_t action);
634 static struct match_char *already_in_tree(struct match_char *current, char *pat, int is_pattern);
635 static struct match_char *add_exten_to_pattern_tree(struct ast_context *con,
636                 struct ast_exten *e1, int findonly);
637 static void create_match_char_tree(struct ast_context *con);
638 static struct ast_exten *get_canmatch_exten(struct match_char *node);
639 static void destroy_pattern_tree(struct match_char *pattern_tree);
640 static int hashtab_compare_extens(const void *ha_a, const void *ah_b);
641 static int hashtab_compare_exten_numbers(const void *ah_a, const void *ah_b);
642 static int hashtab_compare_exten_labels(const void *ah_a, const void *ah_b);
643 static unsigned int hashtab_hash_extens(const void *obj);
644 static unsigned int hashtab_hash_priority(const void *obj);
645 static unsigned int hashtab_hash_labels(const void *obj);
646 static void __ast_internal_context_destroy( struct ast_context *con);
647 static int ast_add_extension_nolock(const char *context, int replace, const char *extension,
648         int priority, const char *label, const char *callerid,
649         const char *application, void *data, void (*datad)(void *), const char *registrar);
650 static int ast_add_extension2_lockopt(struct ast_context *con,
651         int replace, const char *extension, int priority, const char *label, const char *callerid,
652         const char *application, void *data, void (*datad)(void *),
653         const char *registrar, int lock_context);
654 static struct ast_context *find_context_locked(const char *context);
655 static struct ast_context *find_context(const char *context);
656 static void get_device_state_causing_channels(struct ao2_container *c);
657 static int ext_strncpy(char *dst, const char *src, int len, int nofluff);
658
659 /*!
660  * \internal
661  * \brief Character array comparison function for qsort.
662  *
663  * \param a Left side object.
664  * \param b Right side object.
665  *
666  * \retval <0 if a < b
667  * \retval =0 if a = b
668  * \retval >0 if a > b
669  */
670 static int compare_char(const void *a, const void *b)
671 {
672         const unsigned char *ac = a;
673         const unsigned char *bc = b;
674
675         return *ac - *bc;
676 }
677
678 /* labels, contexts are case sensitive  priority numbers are ints */
679 int ast_hashtab_compare_contexts(const void *ah_a, const void *ah_b)
680 {
681         const struct ast_context *ac = ah_a;
682         const struct ast_context *bc = ah_b;
683         if (!ac || !bc) /* safety valve, but it might prevent a crash you'd rather have happen */
684                 return 1;
685         /* assume context names are registered in a string table! */
686         return strcmp(ac->name, bc->name);
687 }
688
689 static int hashtab_compare_extens(const void *ah_a, const void *ah_b)
690 {
691         const struct ast_exten *ac = ah_a;
692         const struct ast_exten *bc = ah_b;
693         int x = strcmp(ac->exten, bc->exten);
694         if (x) { /* if exten names are diff, then return */
695                 return x;
696         }
697
698         /* but if they are the same, do the cidmatch values match? */
699         /* not sure which side may be using ast_ext_matchcid_types, so check both */
700         if (ac->matchcid == AST_EXT_MATCHCID_ANY || bc->matchcid == AST_EXT_MATCHCID_ANY) {
701                 return 0;
702         }
703         if (ac->matchcid == AST_EXT_MATCHCID_OFF && bc->matchcid == AST_EXT_MATCHCID_OFF) {
704                 return 0;
705         }
706         if (ac->matchcid != bc->matchcid) {
707                 return 1;
708         }
709         /* all other cases already disposed of, match now required on callerid string (cidmatch) */
710         /* although ast_add_extension2_lockopt() enforces non-zero ptr, caller may not have */
711         if (ast_strlen_zero(ac->cidmatch) && ast_strlen_zero(bc->cidmatch)) {
712                 return 0;
713         }
714         return strcmp(ac->cidmatch, bc->cidmatch);
715 }
716
717 static int hashtab_compare_exten_numbers(const void *ah_a, const void *ah_b)
718 {
719         const struct ast_exten *ac = ah_a;
720         const struct ast_exten *bc = ah_b;
721         return ac->priority != bc->priority;
722 }
723
724 static int hashtab_compare_exten_labels(const void *ah_a, const void *ah_b)
725 {
726         const struct ast_exten *ac = ah_a;
727         const struct ast_exten *bc = ah_b;
728         return strcmp(S_OR(ac->label, ""), S_OR(bc->label, ""));
729 }
730
731 unsigned int ast_hashtab_hash_contexts(const void *obj)
732 {
733         const struct ast_context *ac = obj;
734         return ast_hashtab_hash_string(ac->name);
735 }
736
737 static unsigned int hashtab_hash_extens(const void *obj)
738 {
739         const struct ast_exten *ac = obj;
740         unsigned int x = ast_hashtab_hash_string(ac->exten);
741         unsigned int y = 0;
742         if (ac->matchcid == AST_EXT_MATCHCID_ON)
743                 y = ast_hashtab_hash_string(ac->cidmatch);
744         return x+y;
745 }
746
747 static unsigned int hashtab_hash_priority(const void *obj)
748 {
749         const struct ast_exten *ac = obj;
750         return ast_hashtab_hash_int(ac->priority);
751 }
752
753 static unsigned int hashtab_hash_labels(const void *obj)
754 {
755         const struct ast_exten *ac = obj;
756         return ast_hashtab_hash_string(S_OR(ac->label, ""));
757 }
758
759 static int autofallthrough = 1;
760 static int extenpatternmatchnew = 0;
761 static char *overrideswitch = NULL;
762
763 /*! \brief Subscription for device state change events */
764 static struct stasis_subscription *device_state_sub;
765 /*! \brief Subscription for presence state change events */
766 static struct stasis_subscription *presence_state_sub;
767
768 AST_MUTEX_DEFINE_STATIC(maxcalllock);
769 static int countcalls;
770 static int totalcalls;
771
772 static struct ast_context *contexts;
773 static struct ast_hashtab *contexts_table = NULL;
774
775 /*!
776  * \brief Lock for the ast_context list
777  * \note
778  * This lock MUST be recursive, or a deadlock on reload may result.  See
779  * https://issues.asterisk.org/view.php?id=17643
780  */
781 AST_MUTEX_DEFINE_STATIC(conlock);
782
783 /*!
784  * \brief Lock to hold off restructuring of hints by ast_merge_contexts_and_delete.
785  */
786 AST_MUTEX_DEFINE_STATIC(context_merge_lock);
787
788 static int stateid = 1;
789 /*!
790  * \note When holding this container's lock, do _not_ do
791  * anything that will cause conlock to be taken, unless you
792  * _already_ hold it.  The ast_merge_contexts_and_delete function
793  * will take the locks in conlock/hints order, so any other
794  * paths that require both locks must also take them in that
795  * order.
796  */
797 static struct ao2_container *hints;
798
799 static struct ao2_container *statecbs;
800
801 #ifdef CONTEXT_DEBUG
802
803 /* these routines are provided for doing run-time checks
804    on the extension structures, in case you are having
805    problems, this routine might help you localize where
806    the problem is occurring. It's kinda like a debug memory
807    allocator's arena checker... It'll eat up your cpu cycles!
808    but you'll see, if you call it in the right places,
809    right where your problems began...
810 */
811
812 /* you can break on the check_contexts_trouble()
813 routine in your debugger to stop at the moment
814 there's a problem */
815 void check_contexts_trouble(void);
816
817 void check_contexts_trouble(void)
818 {
819         int x = 1;
820         x = 2;
821 }
822
823 int check_contexts(char *, int);
824
825 int check_contexts(char *file, int line )
826 {
827         struct ast_hashtab_iter *t1;
828         struct ast_context *c1, *c2;
829         int found = 0;
830         struct ast_exten *e1, *e2, *e3;
831         struct ast_exten ex;
832
833         /* try to find inconsistencies */
834         /* is every context in the context table in the context list and vice-versa ? */
835
836         if (!contexts_table) {
837                 ast_log(LOG_NOTICE,"Called from: %s:%d: No contexts_table!\n", file, line);
838                 usleep(500000);
839         }
840
841         t1 = ast_hashtab_start_traversal(contexts_table);
842         while( (c1 = ast_hashtab_next(t1))) {
843                 for(c2=contexts;c2;c2=c2->next) {
844                         if (!strcmp(c1->name, c2->name)) {
845                                 found = 1;
846                                 break;
847                         }
848                 }
849                 if (!found) {
850                         ast_log(LOG_NOTICE,"Called from: %s:%d: Could not find the %s context in the linked list\n", file, line, c1->name);
851                         check_contexts_trouble();
852                 }
853         }
854         ast_hashtab_end_traversal(t1);
855         for(c2=contexts;c2;c2=c2->next) {
856                 c1 = find_context_locked(c2->name);
857                 if (!c1) {
858                         ast_log(LOG_NOTICE,"Called from: %s:%d: Could not find the %s context in the hashtab\n", file, line, c2->name);
859                         check_contexts_trouble();
860                 } else
861                         ast_unlock_contexts();
862         }
863
864         /* loop thru all contexts, and verify the exten structure compares to the
865            hashtab structure */
866         for(c2=contexts;c2;c2=c2->next) {
867                 c1 = find_context_locked(c2->name);
868                 if (c1) {
869                         ast_unlock_contexts();
870
871                         /* is every entry in the root list also in the root_table? */
872                         for(e1 = c1->root; e1; e1=e1->next)
873                         {
874                                 char dummy_name[1024];
875                                 ex.exten = dummy_name;
876                                 ex.matchcid = e1->matchcid;
877                                 ex.cidmatch = e1->cidmatch;
878                                 ast_copy_string(dummy_name, e1->exten, sizeof(dummy_name));
879                                 e2 = ast_hashtab_lookup(c1->root_table, &ex);
880                                 if (!e2) {
881                                         if (e1->matchcid == AST_EXT_MATCHCID_ON) {
882                                                 ast_log(LOG_NOTICE, "Called from: %s:%d: The %s context records "
883                                                         "the exten %s (CID match: %s) but it is not in its root_table\n",
884                                                         file, line, c2->name, dummy_name, e1->cidmatch_display);
885                                         } else {
886                                                 ast_log(LOG_NOTICE, "Called from: %s:%d: The %s context records "
887                                                         "the exten %s but it is not in its root_table\n",
888                                                         file, line, c2->name, dummy_name);
889                                         }
890                                         check_contexts_trouble();
891                                 }
892                         }
893
894                         /* is every entry in the root_table also in the root list? */
895                         if (!c2->root_table) {
896                                 if (c2->root) {
897                                         ast_log(LOG_NOTICE,"Called from: %s:%d: No c2->root_table for context %s!\n", file, line, c2->name);
898                                         usleep(500000);
899                                 }
900                         } else {
901                                 t1 = ast_hashtab_start_traversal(c2->root_table);
902                                 while( (e2 = ast_hashtab_next(t1)) ) {
903                                         for(e1=c2->root;e1;e1=e1->next) {
904                                                 if (!strcmp(e1->exten, e2->exten)) {
905                                                         found = 1;
906                                                         break;
907                                                 }
908                                         }
909                                         if (!found) {
910                                                 ast_log(LOG_NOTICE,"Called from: %s:%d: The %s context records the exten %s but it is not in its root_table\n", file, line, c2->name, e2->exten);
911                                                 check_contexts_trouble();
912                                         }
913
914                                 }
915                                 ast_hashtab_end_traversal(t1);
916                         }
917                 }
918                 /* is every priority reflected in the peer_table at the head of the list? */
919
920                 /* is every entry in the root list also in the root_table? */
921                 /* are the per-extension peer_tables in the right place? */
922
923                 for(e1 = c2->root; e1; e1 = e1->next) {
924
925                         for(e2=e1;e2;e2=e2->peer) {
926                                 ex.priority = e2->priority;
927                                 if (e2 != e1 && e2->peer_table) {
928                                         ast_log(LOG_NOTICE,"Called from: %s:%d: The %s context, %s exten, %d priority has a peer_table entry, and shouldn't!\n", file, line, c2->name, e1->exten, e2->priority );
929                                         check_contexts_trouble();
930                                 }
931
932                                 if (e2 != e1 && e2->peer_label_table) {
933                                         ast_log(LOG_NOTICE,"Called from: %s:%d: The %s context, %s exten, %d priority has a peer_label_table entry, and shouldn't!\n", file, line, c2->name, e1->exten, e2->priority );
934                                         check_contexts_trouble();
935                                 }
936
937                                 if (e2 == e1 && !e2->peer_table){
938                                         ast_log(LOG_NOTICE,"Called from: %s:%d: The %s context, %s exten, %d priority doesn't have a peer_table!\n", file, line, c2->name, e1->exten, e2->priority );
939                                         check_contexts_trouble();
940                                 }
941
942                                 if (e2 == e1 && !e2->peer_label_table) {
943                                         ast_log(LOG_NOTICE,"Called from: %s:%d: The %s context, %s exten, %d priority doesn't have a peer_label_table!\n", file, line, c2->name, e1->exten, e2->priority );
944                                         check_contexts_trouble();
945                                 }
946
947
948                                 e3 = ast_hashtab_lookup(e1->peer_table, &ex);
949                                 if (!e3) {
950                                         ast_log(LOG_NOTICE,"Called from: %s:%d: The %s context, %s exten, %d priority is not reflected in the peer_table\n", file, line, c2->name, e1->exten, e2->priority );
951                                         check_contexts_trouble();
952                                 }
953                         }
954
955                         if (!e1->peer_table){
956                                 ast_log(LOG_NOTICE,"Called from: %s:%d: No e1->peer_table!\n", file, line);
957                                 usleep(500000);
958                         }
959
960                         /* is every entry in the peer_table also in the peer list? */
961                         t1 = ast_hashtab_start_traversal(e1->peer_table);
962                         while( (e2 = ast_hashtab_next(t1)) ) {
963                                 for(e3=e1;e3;e3=e3->peer) {
964                                         if (e3->priority == e2->priority) {
965                                                 found = 1;
966                                                 break;
967                                         }
968                                 }
969                                 if (!found) {
970                                         ast_log(LOG_NOTICE,"Called from: %s:%d: The %s context, %s exten, %d priority is not reflected in the peer list\n", file, line, c2->name, e1->exten, e2->priority );
971                                         check_contexts_trouble();
972                                 }
973                         }
974                         ast_hashtab_end_traversal(t1);
975                 }
976         }
977         return 0;
978 }
979 #endif
980
981 static void pbx_destroy(struct ast_pbx *p)
982 {
983         ast_free(p);
984 }
985
986 /* form a tree that fully describes all the patterns in a context's extensions
987  * in this tree, a "node" represents an individual character or character set
988  * meant to match the corresponding character in a dial string. The tree
989  * consists of a series of match_char structs linked in a chain
990  * via the alt_char pointers. More than one pattern can share the same parts of the
991  * tree as other extensions with the same pattern to that point.
992  * My first attempt to duplicate the finding of the 'best' pattern was flawed in that
993  * I misunderstood the general algorithm. I thought that the 'best' pattern
994  * was the one with lowest total score. This was not true. Thus, if you have
995  * patterns "1XXXXX" and "X11111", you would be tempted to say that "X11111" is
996  * the "best" match because it has fewer X's, and is therefore more specific,
997  * but this is not how the old algorithm works. It sorts matching patterns
998  * in a similar collating sequence as sorting alphabetic strings, from left to
999  * right. Thus, "1XXXXX" comes before "X11111", and would be the "better" match,
1000  * because "1" is more specific than "X".
1001  * So, to accomodate this philosophy, I sort the tree branches along the alt_char
1002  * line so they are lowest to highest in specificity numbers. This way, as soon
1003  * as we encounter our first complete match, we automatically have the "best"
1004  * match and can stop the traversal immediately. Same for CANMATCH/MATCHMORE.
1005  * If anyone would like to resurrect the "wrong" pattern trie searching algorithm,
1006  * they are welcome to revert pbx to before 1 Apr 2008.
1007  * As an example, consider these 4 extensions:
1008  * (a) NXXNXXXXXX
1009  * (b) 307754XXXX
1010  * (c) fax
1011  * (d) NXXXXXXXXX
1012  *
1013  * In the above, between (a) and (d), (a) is a more specific pattern than (d), and would win over
1014  * most numbers. For all numbers beginning with 307754, (b) should always win.
1015  *
1016  * These pattern should form a (sorted) tree that looks like this:
1017  *   { "3" }  --next-->  { "0" }  --next--> { "7" } --next--> { "7" } --next--> { "5" } ... blah ... --> { "X" exten_match: (b) }
1018  *      |
1019  *      |alt
1020  *      |
1021  *   { "f" }  --next-->  { "a" }  --next--> { "x"  exten_match: (c) }
1022  *   { "N" }  --next-->  { "X" }  --next--> { "X" } --next--> { "N" } --next--> { "X" } ... blah ... --> { "X" exten_match: (a) }
1023  *      |                                                        |
1024  *      |                                                        |alt
1025  *      |alt                                                     |
1026  *      |                                                     { "X" } --next--> { "X" } ... blah ... --> { "X" exten_match: (d) }
1027  *      |
1028  *     NULL
1029  *
1030  *   In the above, I could easily turn "N" into "23456789", but I think that a quick "if( *z >= '2' && *z <= '9' )" might take
1031  *   fewer CPU cycles than a call to strchr("23456789",*z), where *z is the char to match...
1032  *
1033  *   traversal is pretty simple: one routine merely traverses the alt list, and for each matching char in the pattern,  it calls itself
1034  *   on the corresponding next pointer, incrementing also the pointer of the string to be matched, and passing the total specificity and length.
1035  *   We pass a pointer to a scoreboard down through, also.
1036  *   The scoreboard isn't as necessary to the revised algorithm, but I kept it as a handy way to return the matched extension.
1037  *   The first complete match ends the traversal, which should make this version of the pattern matcher faster
1038  *   the previous. The same goes for "CANMATCH" or "MATCHMORE"; the first such match ends the traversal. In both
1039  *   these cases, the reason we can stop immediately, is because the first pattern match found will be the "best"
1040  *   according to the sort criteria.
1041  *   Hope the limit on stack depth won't be a problem... this routine should
1042  *   be pretty lean as far a stack usage goes. Any non-match terminates the recursion down a branch.
1043  *
1044  *   In the above example, with the number "3077549999" as the pattern, the traversor could match extensions a, b and d.  All are
1045  *   of length 10; they have total specificities of  24580, 10246, and 25090, respectively, not that this matters
1046  *   at all. (b) wins purely because the first character "3" is much more specific (lower specificity) than "N". I have
1047  *   left the specificity totals in the code as an artifact; at some point, I will strip it out.
1048  *
1049  *   Just how much time this algorithm might save over a plain linear traversal over all possible patterns is unknown,
1050  *   because it's a function of how many extensions are stored in a context. With thousands of extensions, the speedup
1051  *   can be very noticeable. The new matching algorithm can run several hundreds of times faster, if not a thousand or
1052  *   more times faster in extreme cases.
1053  *
1054  *   MatchCID patterns are also supported, and stored in the tree just as the extension pattern is. Thus, you
1055  *   can have patterns in your CID field as well.
1056  *
1057  * */
1058
1059
1060 static void update_scoreboard(struct scoreboard *board, int length, int spec, struct ast_exten *exten, char last, const char *callerid, int deleted, struct match_char *node)
1061 {
1062         /* if this extension is marked as deleted, then skip this -- if it never shows
1063            on the scoreboard, it will never be found, nor will halt the traversal. */
1064         if (deleted)
1065                 return;
1066         board->total_specificity = spec;
1067         board->total_length = length;
1068         board->exten = exten;
1069         board->last_char = last;
1070         board->node = node;
1071 #ifdef NEED_DEBUG_HERE
1072         ast_log(LOG_NOTICE,"Scoreboarding (LONGER) %s, len=%d, score=%d\n", exten->exten, length, spec);
1073 #endif
1074 }
1075
1076 #ifdef NEED_DEBUG
1077 static void log_match_char_tree(struct match_char *node, char *prefix)
1078 {
1079         char extenstr[40];
1080         struct ast_str *my_prefix = ast_str_alloca(1024);
1081
1082         extenstr[0] = '\0';
1083
1084         if (node && node->exten)
1085                 snprintf(extenstr, sizeof(extenstr), "(%p)", node->exten);
1086
1087         if (strlen(node->x) > 1) {
1088                 ast_debug(1, "%s[%s]:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y':'N',
1089                         node->deleted? 'D':'-', node->specificity, node->exten? "EXTEN:":"",
1090                         node->exten ? node->exten->exten : "", extenstr);
1091         } else {
1092                 ast_debug(1, "%s%s:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y':'N',
1093                         node->deleted? 'D':'-', node->specificity, node->exten? "EXTEN:":"",
1094                         node->exten ? node->exten->exten : "", extenstr);
1095         }
1096
1097         ast_str_set(&my_prefix, 0, "%s+       ", prefix);
1098
1099         if (node->next_char)
1100                 log_match_char_tree(node->next_char, ast_str_buffer(my_prefix));
1101
1102         if (node->alt_char)
1103                 log_match_char_tree(node->alt_char, prefix);
1104 }
1105 #endif
1106
1107 static void cli_match_char_tree(struct match_char *node, char *prefix, int fd)
1108 {
1109         char extenstr[40];
1110         struct ast_str *my_prefix = ast_str_alloca(1024);
1111
1112         extenstr[0] = '\0';
1113
1114         if (node->exten) {
1115                 snprintf(extenstr, sizeof(extenstr), "(%p)", node->exten);
1116         }
1117
1118         if (strlen(node->x) > 1) {
1119                 ast_cli(fd, "%s[%s]:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y' : 'N',
1120                         node->deleted ? 'D' : '-', node->specificity, node->exten? "EXTEN:" : "",
1121                         node->exten ? node->exten->name : "", extenstr);
1122         } else {
1123                 ast_cli(fd, "%s%s:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y' : 'N',
1124                         node->deleted ? 'D' : '-', node->specificity, node->exten? "EXTEN:" : "",
1125                         node->exten ? node->exten->name : "", extenstr);
1126         }
1127
1128         ast_str_set(&my_prefix, 0, "%s+       ", prefix);
1129
1130         if (node->next_char)
1131                 cli_match_char_tree(node->next_char, ast_str_buffer(my_prefix), fd);
1132
1133         if (node->alt_char)
1134                 cli_match_char_tree(node->alt_char, prefix, fd);
1135 }
1136
1137 static struct ast_exten *get_canmatch_exten(struct match_char *node)
1138 {
1139         /* find the exten at the end of the rope */
1140         struct match_char *node2 = node;
1141
1142         for (node2 = node; node2; node2 = node2->next_char) {
1143                 if (node2->exten) {
1144 #ifdef NEED_DEBUG_HERE
1145                         ast_log(LOG_NOTICE,"CanMatch_exten returns exten %s(%p)\n", node2->exten->exten, node2->exten);
1146 #endif
1147                         return node2->exten;
1148                 }
1149         }
1150 #ifdef NEED_DEBUG_HERE
1151         ast_log(LOG_NOTICE,"CanMatch_exten returns NULL, match_char=%s\n", node->x);
1152 #endif
1153         return 0;
1154 }
1155
1156 static struct ast_exten *trie_find_next_match(struct match_char *node)
1157 {
1158         struct match_char *m3;
1159         struct match_char *m4;
1160         struct ast_exten *e3;
1161
1162         if (node && node->x[0] == '.' && !node->x[1]) { /* dot and ! will ALWAYS be next match in a matchmore */
1163                 return node->exten;
1164         }
1165
1166         if (node && node->x[0] == '!' && !node->x[1]) {
1167                 return node->exten;
1168         }
1169
1170         if (!node || !node->next_char) {
1171                 return NULL;
1172         }
1173
1174         m3 = node->next_char;
1175
1176         if (m3->exten) {
1177                 return m3->exten;
1178         }
1179         for (m4 = m3->alt_char; m4; m4 = m4->alt_char) {
1180                 if (m4->exten) {
1181                         return m4->exten;
1182                 }
1183         }
1184         for (m4 = m3; m4; m4 = m4->alt_char) {
1185                 e3 = trie_find_next_match(m3);
1186                 if (e3) {
1187                         return e3;
1188                 }
1189         }
1190
1191         return NULL;
1192 }
1193
1194 #ifdef DEBUG_THIS
1195 static char *action2str(enum ext_match_t action)
1196 {
1197         switch (action) {
1198         case E_MATCH:
1199                 return "MATCH";
1200         case E_CANMATCH:
1201                 return "CANMATCH";
1202         case E_MATCHMORE:
1203                 return "MATCHMORE";
1204         case E_FINDLABEL:
1205                 return "FINDLABEL";
1206         case E_SPAWN:
1207                 return "SPAWN";
1208         default:
1209                 return "?ACTION?";
1210         }
1211 }
1212
1213 #endif
1214
1215 static void new_find_extension(const char *str, struct scoreboard *score, struct match_char *tree, int length, int spec, const char *callerid, const char *label, enum ext_match_t action)
1216 {
1217         struct match_char *p; /* note minimal stack storage requirements */
1218         struct ast_exten pattern = { .label = label };
1219 #ifdef DEBUG_THIS
1220         if (tree)
1221                 ast_log(LOG_NOTICE,"new_find_extension called with %s on (sub)tree %s action=%s\n", str, tree->x, action2str(action));
1222         else
1223                 ast_log(LOG_NOTICE,"new_find_extension called with %s on (sub)tree NULL action=%s\n", str, action2str(action));
1224 #endif
1225         for (p = tree; p; p = p->alt_char) {
1226                 if (p->is_pattern) {
1227                         if (p->x[0] == 'N') {
1228                                 if (p->x[1] == 0 && *str >= '2' && *str <= '9' ) {
1229 #define NEW_MATCHER_CHK_MATCH          \
1230                                         if (p->exten && !(*(str + 1))) { /* if a shorter pattern matches along the way, might as well report it */             \
1231                                                 if (action == E_MATCH || action == E_SPAWN || action == E_FINDLABEL) { /* if in CANMATCH/MATCHMORE, don't let matches get in the way */   \
1232                                                         update_scoreboard(score, length + 1, spec + p->specificity, p->exten, 0, callerid, p->deleted, p);                 \
1233                                                         if (!p->deleted) {                                                                                           \
1234                                                                 if (action == E_FINDLABEL) {                                                                             \
1235                                                                         if (ast_hashtab_lookup(score->exten->peer_label_table, &pattern)) {                                  \
1236                                                                                 ast_debug(4, "Found label in preferred extension\n");                                            \
1237                                                                                 return;                                                                                          \
1238                                                                         }                                                                                                    \
1239                                                                 } else {                                                                                                 \
1240                                                                         ast_debug(4, "returning an exact match-- first found-- %s\n", p->exten->name);                       \
1241                                                                         return; /* the first match, by definition, will be the best, because of the sorted tree */           \
1242                                                                 }                                                                                                        \
1243                                                         }                                                                                                            \
1244                                                 }                                                                                                                \
1245                                         }
1246
1247 #define NEW_MATCHER_RECURSE                \
1248                                         if (p->next_char && (*(str + 1) || (p->next_char->x[0] == '/' && p->next_char->x[1] == 0)                 \
1249                                                        || p->next_char->x[0] == '!')) {                                          \
1250                                                 if (*(str + 1) || p->next_char->x[0] == '!') {                                                         \
1251                                                         new_find_extension(str + 1, score, p->next_char, length + 1, spec + p->specificity, callerid, label, action); \
1252                                                         if (score->exten)  {                                                                             \
1253                                                         ast_debug(4 ,"returning an exact match-- %s\n", score->exten->name);                         \
1254                                                                 return; /* the first match is all we need */                                                 \
1255                                                         }                                                                                                                                                \
1256                                                 } else {                                                                                             \
1257                                                         new_find_extension("/", score, p->next_char, length + 1, spec + p->specificity, callerid, label, action);        \
1258                                                         if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {      \
1259                                                         ast_debug(4,"returning a (can/more) match--- %s\n", score->exten ? score->exten->name :      \
1260                                                "NULL");                                                                        \
1261                                                                 return; /* the first match is all we need */                                                 \
1262                                                         }                                                                                                                                                \
1263                                                 }                                                                                                    \
1264                                         } else if ((p->next_char || action == E_CANMATCH) && !*(str + 1)) {                                                                  \
1265                                                 score->canmatch = 1;                                                                                 \
1266                                                 score->canmatch_exten = get_canmatch_exten(p);                                                       \
1267                                                 if (action == E_CANMATCH || action == E_MATCHMORE) {                                                 \
1268                                                 ast_debug(4, "returning a canmatch/matchmore--- str=%s\n", str);                                  \
1269                                                         return;                                                                                          \
1270                                                 }                                                                                                                                                    \
1271                                         }
1272
1273                                         NEW_MATCHER_CHK_MATCH;
1274                                         NEW_MATCHER_RECURSE;
1275                                 }
1276                         } else if (p->x[0] == 'Z') {
1277                                 if (p->x[1] == 0 && *str >= '1' && *str <= '9' ) {
1278                                         NEW_MATCHER_CHK_MATCH;
1279                                         NEW_MATCHER_RECURSE;
1280                                 }
1281                         } else if (p->x[0] == 'X') {
1282                                 if (p->x[1] == 0 && *str >= '0' && *str <= '9' ) {
1283                                         NEW_MATCHER_CHK_MATCH;
1284                                         NEW_MATCHER_RECURSE;
1285                                 }
1286                         } else if (p->x[0] == '.' && p->x[1] == 0) {
1287                                 /* how many chars will the . match against? */
1288                                 int i = 0;
1289                                 const char *str2 = str;
1290                                 while (*str2 && *str2 != '/') {
1291                                         str2++;
1292                                         i++;
1293                                 }
1294                                 if (p->exten && *str2 != '/') {
1295                                         update_scoreboard(score, length + i, spec + (i * p->specificity), p->exten, '.', callerid, p->deleted, p);
1296                                         if (score->exten) {
1297                                                 ast_debug(4, "return because scoreboard has a match with '/'--- %s\n",
1298                                                         score->exten->name);
1299                                                 return; /* the first match is all we need */
1300                                         }
1301                                 }
1302                                 if (p->next_char && p->next_char->x[0] == '/' && p->next_char->x[1] == 0) {
1303                                         new_find_extension("/", score, p->next_char, length + i, spec+(p->specificity*i), callerid, label, action);
1304                                         if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
1305                                                 ast_debug(4, "return because scoreboard has exact match OR "
1306                                                         "CANMATCH/MATCHMORE & canmatch set--- %s\n",
1307                                                         score->exten ? score->exten->name : "NULL");
1308                                                 return; /* the first match is all we need */
1309                                         }
1310                                 }
1311                         } else if (p->x[0] == '!' && p->x[1] == 0) {
1312                                 /* how many chars will the . match against? */
1313                                 int i = 1;
1314                                 const char *str2 = str;
1315                                 while (*str2 && *str2 != '/') {
1316                                         str2++;
1317                                         i++;
1318                                 }
1319                                 if (p->exten && *str2 != '/') {
1320                                         update_scoreboard(score, length + 1, spec + (p->specificity * i), p->exten, '!', callerid, p->deleted, p);
1321                                         if (score->exten) {
1322                                                 ast_debug(4, "return because scoreboard has a '!' match--- %s\n",
1323                                                         score->exten->name);
1324                                                 return; /* the first match is all we need */
1325                                         }
1326                                 }
1327                                 if (p->next_char && p->next_char->x[0] == '/' && p->next_char->x[1] == 0) {
1328                                         new_find_extension("/", score, p->next_char, length + i, spec + (p->specificity * i), callerid, label, action);
1329                                         if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
1330                                                 ast_debug(4, "return because scoreboard has exact match OR "
1331                                                         "CANMATCH/MATCHMORE & canmatch set with '/' and '!'--- %s\n",
1332                                                         score->exten ? score->exten->name : "NULL");
1333                                                 return; /* the first match is all we need */
1334                                         }
1335                                 }
1336                         } else if (p->x[0] == '/' && p->x[1] == 0) {
1337                                 /* the pattern in the tree includes the cid match! */
1338                                 if (p->next_char && callerid && *callerid) {
1339                                         new_find_extension(callerid, score, p->next_char, length + 1, spec, callerid, label, action);
1340                                         if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
1341                                                 ast_debug(4, "return because scoreboard has exact match OR "
1342                                                         "CANMATCH/MATCHMORE & canmatch set with '/'--- %s\n",
1343                                                         score->exten ? score->exten->name : "NULL");
1344                                                 return; /* the first match is all we need */
1345                                         }
1346                                 }
1347                         } else if (strchr(p->x, *str)) {
1348                                 ast_debug(4, "Nothing strange about this match\n");
1349                                 NEW_MATCHER_CHK_MATCH;
1350                                 NEW_MATCHER_RECURSE;
1351                         }
1352                 } else if (strchr(p->x, *str)) {
1353                         ast_debug(4, "Nothing strange about this match\n");
1354                         NEW_MATCHER_CHK_MATCH;
1355                         NEW_MATCHER_RECURSE;
1356                 }
1357         }
1358         ast_debug(4, "return at end of func\n");
1359 }
1360
1361 /* the algorithm for forming the extension pattern tree is also a bit simple; you
1362  * traverse all the extensions in a context, and for each char of the extension,
1363  * you see if it exists in the tree; if it doesn't, you add it at the appropriate
1364  * spot. What more can I say? At the end of each exten, you cap it off by adding the
1365  * address of the extension involved. Duplicate patterns will be complained about.
1366  *
1367  * Ideally, this would be done for each context after it is created and fully
1368  * filled. It could be done as a finishing step after extensions.conf or .ael is
1369  * loaded, or it could be done when the first search is encountered. It should only
1370  * have to be done once, until the next unload or reload.
1371  *
1372  * I guess forming this pattern tree would be analogous to compiling a regex. Except
1373  * that a regex only handles 1 pattern, really. This trie holds any number
1374  * of patterns. Well, really, it **could** be considered a single pattern,
1375  * where the "|" (or) operator is allowed, I guess, in a way, sort of...
1376  */
1377
1378 static struct match_char *already_in_tree(struct match_char *current, char *pat, int is_pattern)
1379 {
1380         struct match_char *t;
1381
1382         if (!current) {
1383                 return 0;
1384         }
1385
1386         for (t = current; t; t = t->alt_char) {
1387                 if (is_pattern == t->is_pattern && !strcmp(pat, t->x)) {/* uh, we may want to sort exploded [] contents to make matching easy */
1388                         return t;
1389                 }
1390         }
1391
1392         return 0;
1393 }
1394
1395 /* The first arg is the location of the tree ptr, or the
1396    address of the next_char ptr in the node, so we can mess
1397    with it, if we need to insert at the beginning of the list */
1398
1399 static void insert_in_next_chars_alt_char_list(struct match_char **parent_ptr, struct match_char *node)
1400 {
1401         struct match_char *curr, *lcurr;
1402
1403         /* insert node into the tree at "current", so the alt_char list from current is
1404            sorted in increasing value as you go to the leaves */
1405         if (!(*parent_ptr)) {
1406                 *parent_ptr = node;
1407                 return;
1408         }
1409
1410         if ((*parent_ptr)->specificity > node->specificity) {
1411                 /* insert at head */
1412                 node->alt_char = (*parent_ptr);
1413                 *parent_ptr = node;
1414                 return;
1415         }
1416
1417         lcurr = *parent_ptr;
1418         for (curr = (*parent_ptr)->alt_char; curr; curr = curr->alt_char) {
1419                 if (curr->specificity > node->specificity) {
1420                         node->alt_char = curr;
1421                         lcurr->alt_char = node;
1422                         break;
1423                 }
1424                 lcurr = curr;
1425         }
1426
1427         if (!curr) {
1428                 lcurr->alt_char = node;
1429         }
1430
1431 }
1432
1433 struct pattern_node {
1434         /*! Pattern node specificity */
1435         int specif;
1436         /*! Pattern node match characters. */
1437         char buf[256];
1438 };
1439
1440 static struct match_char *add_pattern_node(struct ast_context *con, struct match_char *current, const struct pattern_node *pattern, int is_pattern, int already, struct match_char **nextcharptr)
1441 {
1442         struct match_char *m;
1443
1444         if (!(m = ast_calloc(1, sizeof(*m) + strlen(pattern->buf)))) {
1445                 return NULL;
1446         }
1447
1448         /* strcpy is safe here since we know its size and have allocated
1449          * just enough space for when we allocated m
1450          */
1451         strcpy(m->x, pattern->buf);
1452
1453         /* the specificity scores are the same as used in the old
1454            pattern matcher. */
1455         m->is_pattern = is_pattern;
1456         if (pattern->specif == 1 && is_pattern && pattern->buf[0] == 'N') {
1457                 m->specificity = 0x0832;
1458         } else if (pattern->specif == 1 && is_pattern && pattern->buf[0] == 'Z') {
1459                 m->specificity = 0x0931;
1460         } else if (pattern->specif == 1 && is_pattern && pattern->buf[0] == 'X') {
1461                 m->specificity = 0x0a30;
1462         } else if (pattern->specif == 1 && is_pattern && pattern->buf[0] == '.') {
1463                 m->specificity = 0x18000;
1464         } else if (pattern->specif == 1 && is_pattern && pattern->buf[0] == '!') {
1465                 m->specificity = 0x28000;
1466         } else {
1467                 m->specificity = pattern->specif;
1468         }
1469
1470         if (!con->pattern_tree) {
1471                 insert_in_next_chars_alt_char_list(&con->pattern_tree, m);
1472         } else {
1473                 if (already) { /* switch to the new regime (traversing vs appending)*/
1474                         insert_in_next_chars_alt_char_list(nextcharptr, m);
1475                 } else {
1476                         insert_in_next_chars_alt_char_list(&current->next_char, m);
1477                 }
1478         }
1479
1480         return m;
1481 }
1482
1483 /*!
1484  * \internal
1485  * \brief Extract the next exten pattern node.
1486  *
1487  * \param node Pattern node to fill.
1488  * \param src Next source character to read.
1489  * \param pattern TRUE if the exten is a pattern.
1490  * \param extenbuf Original exten buffer to use in diagnostic messages.
1491  *
1492  * \retval Ptr to next extenbuf pos to read.
1493  */
1494 static const char *get_pattern_node(struct pattern_node *node, const char *src, int pattern, const char *extenbuf)
1495 {
1496 #define INC_DST_OVERFLOW_CHECK                                                  \
1497         do {                                                                                            \
1498                 if (dst - node->buf < sizeof(node->buf) - 1) {  \
1499                         ++dst;                                                                          \
1500                 } else {                                                                                \
1501                         overflow = 1;                                                           \
1502                 }                                                                                               \
1503         } while (0)
1504
1505         node->specif = 0;
1506         node->buf[0] = '\0';
1507         while (*src) {
1508                 if (*src == '[' && pattern) {
1509                         char *dst = node->buf;
1510                         const char *src_next;
1511                         int length;
1512                         int overflow = 0;
1513
1514                         /* get past the '[' */
1515                         ++src;
1516                         for (;;) {
1517                                 if (*src == '\\') {
1518                                         /* Escaped character. */
1519                                         ++src;
1520                                         if (*src == '[' || *src == '\\' || *src == '-' || *src == ']') {
1521                                                 *dst = *src++;
1522                                                 INC_DST_OVERFLOW_CHECK;
1523                                         }
1524                                 } else if (*src == '-') {
1525                                         unsigned char first;
1526                                         unsigned char last;
1527
1528                                         src_next = src;
1529                                         first = *(src_next - 1);
1530                                         last = *++src_next;
1531
1532                                         if (last == '\\') {
1533                                                 /* Escaped character. */
1534                                                 last = *++src_next;
1535                                         }
1536
1537                                         /* Possible char range. */
1538                                         if (node->buf[0] && last) {
1539                                                 /* Expand the char range. */
1540                                                 while (++first <= last) {
1541                                                         *dst = first;
1542                                                         INC_DST_OVERFLOW_CHECK;
1543                                                 }
1544                                                 src = src_next + 1;
1545                                         } else {
1546                                                 /*
1547                                                  * There was no left or right char for the range.
1548                                                  * It is just a '-'.
1549                                                  */
1550                                                 *dst = *src++;
1551                                                 INC_DST_OVERFLOW_CHECK;
1552                                         }
1553                                 } else if (*src == '\0') {
1554                                         ast_log(LOG_WARNING,
1555                                                 "A matching ']' was not found for '[' in exten pattern '%s'\n",
1556                                                 extenbuf);
1557                                         break;
1558                                 } else if (*src == ']') {
1559                                         ++src;
1560                                         break;
1561                                 } else {
1562                                         *dst = *src++;
1563                                         INC_DST_OVERFLOW_CHECK;
1564                                 }
1565                         }
1566                         /* null terminate the exploded range */
1567                         *dst = '\0';
1568
1569                         if (overflow) {
1570                                 ast_log(LOG_ERROR,
1571                                         "Expanded character set too large to deal with in exten pattern '%s'. Ignoring character set.\n",
1572                                         extenbuf);
1573                                 node->buf[0] = '\0';
1574                                 continue;
1575                         }
1576
1577                         /* Sort the characters in character set. */
1578                         length = strlen(node->buf);
1579                         if (!length) {
1580                                 ast_log(LOG_WARNING, "Empty character set in exten pattern '%s'. Ignoring.\n",
1581                                         extenbuf);
1582                                 node->buf[0] = '\0';
1583                                 continue;
1584                         }
1585                         qsort(node->buf, length, 1, compare_char);
1586
1587                         /* Remove duplicate characters from character set. */
1588                         dst = node->buf;
1589                         src_next = node->buf;
1590                         while (*src_next++) {
1591                                 if (*dst != *src_next) {
1592                                         *++dst = *src_next;
1593                                 }
1594                         }
1595
1596                         length = strlen(node->buf);
1597                         length <<= 8;
1598                         node->specif = length | (unsigned char) node->buf[0];
1599                         break;
1600                 } else if (*src == '-') {
1601                         /* Skip dashes in all extensions. */
1602                         ++src;
1603                 } else {
1604                         if (*src == '\\') {
1605                                 /*
1606                                  * XXX The escape character here does not remove any special
1607                                  * meaning to characters except the '[', '\\', and '-'
1608                                  * characters since they are special only in this function.
1609                                  */
1610                                 node->buf[0] = *++src;
1611                                 if (!node->buf[0]) {
1612                                         break;
1613                                 }
1614                         } else {
1615                                 node->buf[0] = *src;
1616                                 if (pattern) {
1617                                         /* make sure n,x,z patterns are canonicalized to N,X,Z */
1618                                         if (node->buf[0] == 'n') {
1619                                                 node->buf[0] = 'N';
1620                                         } else if (node->buf[0] == 'x') {
1621                                                 node->buf[0] = 'X';
1622                                         } else if (node->buf[0] == 'z') {
1623                                                 node->buf[0] = 'Z';
1624                                         }
1625                                 }
1626                         }
1627                         node->buf[1] = '\0';
1628                         node->specif = 1;
1629                         ++src;
1630                         break;
1631                 }
1632         }
1633         return src;
1634
1635 #undef INC_DST_OVERFLOW_CHECK
1636 }
1637
1638 static struct match_char *add_exten_to_pattern_tree(struct ast_context *con, struct ast_exten *e1, int findonly)
1639 {
1640         struct match_char *m1 = NULL;
1641         struct match_char *m2 = NULL;
1642         struct match_char **m0;
1643         const char *pos;
1644         int already;
1645         int pattern = 0;
1646         int idx_cur;
1647         int idx_next;
1648         char extenbuf[512];
1649         struct pattern_node pat_node[2];
1650
1651         if (e1->matchcid) {
1652                 if (sizeof(extenbuf) < strlen(e1->exten) + strlen(e1->cidmatch) + 2) {
1653                         ast_log(LOG_ERROR,
1654                                 "The pattern %s/%s is too big to deal with: it will be ignored! Disaster!\n",
1655                                 e1->exten, e1->cidmatch);
1656                         return NULL;
1657                 }
1658                 sprintf(extenbuf, "%s/%s", e1->exten, e1->cidmatch);/* Safe.  We just checked. */
1659         } else {
1660                 ast_copy_string(extenbuf, e1->exten, sizeof(extenbuf));
1661         }
1662
1663 #ifdef NEED_DEBUG
1664         ast_debug(1, "Adding exten %s to tree\n", extenbuf);
1665 #endif
1666         m1 = con->pattern_tree; /* each pattern starts over at the root of the pattern tree */
1667         m0 = &con->pattern_tree;
1668         already = 1;
1669
1670         pos = extenbuf;
1671         if (*pos == '_') {
1672                 pattern = 1;
1673                 ++pos;
1674         }
1675         idx_cur = 0;
1676         pos = get_pattern_node(&pat_node[idx_cur], pos, pattern, extenbuf);
1677         for (; pat_node[idx_cur].buf[0]; idx_cur = idx_next) {
1678                 idx_next = (idx_cur + 1) % ARRAY_LEN(pat_node);
1679                 pos = get_pattern_node(&pat_node[idx_next], pos, pattern, extenbuf);
1680
1681                 /* See about adding node to tree. */
1682                 m2 = NULL;
1683                 if (already && (m2 = already_in_tree(m1, pat_node[idx_cur].buf, pattern))
1684                         && m2->next_char) {
1685                         if (!pat_node[idx_next].buf[0]) {
1686                                 /*
1687                                  * This is the end of the pattern, but not the end of the tree.
1688                                  * Mark this node with the exten... a shorter pattern might win
1689                                  * if the longer one doesn't match.
1690                                  */
1691                                 if (findonly) {
1692                                         return m2;
1693                                 }
1694                                 if (m2->exten) {
1695                                         ast_log(LOG_WARNING, "Found duplicate exten. Had %s found %s\n",
1696                                                 m2->deleted ? "(deleted/invalid)" : m2->exten->name, e1->name);
1697                                 }
1698                                 m2->exten = e1;
1699                                 m2->deleted = 0;
1700                         }
1701                         m1 = m2->next_char; /* m1 points to the node to compare against */
1702                         m0 = &m2->next_char; /* m0 points to the ptr that points to m1 */
1703                 } else { /* not already OR not m2 OR nor m2->next_char */
1704                         if (m2) {
1705                                 if (findonly) {
1706                                         return m2;
1707                                 }
1708                                 m1 = m2; /* while m0 stays the same */
1709                         } else {
1710                                 if (findonly) {
1711                                         return m1;
1712                                 }
1713                                 m1 = add_pattern_node(con, m1, &pat_node[idx_cur], pattern, already, m0);
1714                                 if (!m1) { /* m1 is the node just added */
1715                                         return NULL;
1716                                 }
1717                                 m0 = &m1->next_char;
1718                         }
1719                         if (!pat_node[idx_next].buf[0]) {
1720                                 if (m2 && m2->exten) {
1721                                         ast_log(LOG_WARNING, "Found duplicate exten. Had %s found %s\n",
1722                                                 m2->deleted ? "(deleted/invalid)" : m2->exten->name, e1->name);
1723                                 }
1724                                 m1->deleted = 0;
1725                                 m1->exten = e1;
1726                         }
1727
1728                         /* The 'already' variable is a mini-optimization designed to make it so that we
1729                          * don't have to call already_in_tree when we know it will return false.
1730                          */
1731                         already = 0;
1732                 }
1733         }
1734         return m1;
1735 }
1736
1737 static void create_match_char_tree(struct ast_context *con)
1738 {
1739         struct ast_hashtab_iter *t1;
1740         struct ast_exten *e1;
1741 #ifdef NEED_DEBUG
1742         int biggest_bucket, resizes, numobjs, numbucks;
1743
1744         ast_debug(1, "Creating Extension Trie for context %s(%p)\n", con->name, con);
1745         ast_hashtab_get_stats(con->root_table, &biggest_bucket, &resizes, &numobjs, &numbucks);
1746         ast_debug(1, "This tree has %d objects in %d bucket lists, longest list=%d objects, and has resized %d times\n",
1747                         numobjs, numbucks, biggest_bucket, resizes);
1748 #endif
1749         t1 = ast_hashtab_start_traversal(con->root_table);
1750         while ((e1 = ast_hashtab_next(t1))) {
1751                 if (e1->exten) {
1752                         add_exten_to_pattern_tree(con, e1, 0);
1753                 } else {
1754                         ast_log(LOG_ERROR, "Attempt to create extension with no extension name.\n");
1755                 }
1756         }
1757         ast_hashtab_end_traversal(t1);
1758 }
1759
1760 static void destroy_pattern_tree(struct match_char *pattern_tree) /* pattern tree is a simple binary tree, sort of, so the proper way to destroy it is... recursively! */
1761 {
1762         /* destroy all the alternates */
1763         if (pattern_tree->alt_char) {
1764                 destroy_pattern_tree(pattern_tree->alt_char);
1765                 pattern_tree->alt_char = 0;
1766         }
1767         /* destroy all the nexts */
1768         if (pattern_tree->next_char) {
1769                 destroy_pattern_tree(pattern_tree->next_char);
1770                 pattern_tree->next_char = 0;
1771         }
1772         pattern_tree->exten = 0; /* never hurts to make sure there's no pointers laying around */
1773         ast_free(pattern_tree);
1774 }
1775
1776 /*!
1777  * \internal
1778  * \brief Get the length of the exten string.
1779  *
1780  * \param str Exten to get length.
1781  *
1782  * \retval strlen of exten.
1783  */
1784 static int ext_cmp_exten_strlen(const char *str)
1785 {
1786         int len;
1787
1788         len = 0;
1789         for (;;) {
1790                 /* Ignore '-' chars as eye candy fluff. */
1791                 while (*str == '-') {
1792                         ++str;
1793                 }
1794                 if (!*str) {
1795                         break;
1796                 }
1797                 ++str;
1798                 ++len;
1799         }
1800         return len;
1801 }
1802
1803 /*!
1804  * \internal
1805  * \brief Partial comparison of non-pattern extens.
1806  *
1807  * \param left Exten to compare.
1808  * \param right Exten to compare.  Also matches if this string ends first.
1809  *
1810  * \retval <0 if left < right
1811  * \retval =0 if left == right
1812  * \retval >0 if left > right
1813  */
1814 static int ext_cmp_exten_partial(const char *left, const char *right)
1815 {
1816         int cmp;
1817
1818         for (;;) {
1819                 /* Ignore '-' chars as eye candy fluff. */
1820                 while (*left == '-') {
1821                         ++left;
1822                 }
1823                 while (*right == '-') {
1824                         ++right;
1825                 }
1826
1827                 if (!*right) {
1828                         /*
1829                          * Right ended first for partial match or both ended at the same
1830                          * time for a match.
1831                          */
1832                         cmp = 0;
1833                         break;
1834                 }
1835
1836                 cmp = *left - *right;
1837                 if (cmp) {
1838                         break;
1839                 }
1840                 ++left;
1841                 ++right;
1842         }
1843         return cmp;
1844 }
1845
1846 /*!
1847  * \internal
1848  * \brief Comparison of non-pattern extens.
1849  *
1850  * \param left Exten to compare.
1851  * \param right Exten to compare.
1852  *
1853  * \retval <0 if left < right
1854  * \retval =0 if left == right
1855  * \retval >0 if left > right
1856  */
1857 static int ext_cmp_exten(const char *left, const char *right)
1858 {
1859         int cmp;
1860
1861         for (;;) {
1862                 /* Ignore '-' chars as eye candy fluff. */
1863                 while (*left == '-') {
1864                         ++left;
1865                 }
1866                 while (*right == '-') {
1867                         ++right;
1868                 }
1869
1870                 cmp = *left - *right;
1871                 if (cmp) {
1872                         break;
1873                 }
1874                 if (!*left) {
1875                         /*
1876                          * Get here only if both strings ended at the same time.  cmp
1877                          * would be non-zero if only one string ended.
1878                          */
1879                         break;
1880                 }
1881                 ++left;
1882                 ++right;
1883         }
1884         return cmp;
1885 }
1886
1887 /*
1888  * Special characters used in patterns:
1889  *      '_'     underscore is the leading character of a pattern.
1890  *              In other position it is treated as a regular char.
1891  *      '-' The '-' is a separator and ignored.  Why?  So patterns like NXX-XXX-XXXX work.
1892  *      .       one or more of any character. Only allowed at the end of
1893  *              a pattern.
1894  *      !       zero or more of anything. Also impacts the result of CANMATCH
1895  *              and MATCHMORE. Only allowed at the end of a pattern.
1896  *              In the core routine, ! causes a match with a return code of 2.
1897  *              In turn, depending on the search mode: (XXX check if it is implemented)
1898  *              - E_MATCH retuns 1 (does match)
1899  *              - E_MATCHMORE returns 0 (no match)
1900  *              - E_CANMATCH returns 1 (does match)
1901  *
1902  *      /       should not appear as it is considered the separator of the CID info.
1903  *              XXX at the moment we may stop on this char.
1904  *
1905  *      X Z N   match ranges 0-9, 1-9, 2-9 respectively.
1906  *      [       denotes the start of a set of character. Everything inside
1907  *              is considered literally. We can have ranges a-d and individual
1908  *              characters. A '[' and '-' can be considered literally if they
1909  *              are just before ']'.
1910  *              XXX currently there is no way to specify ']' in a range, nor \ is
1911  *              considered specially.
1912  *
1913  * When we compare a pattern with a specific extension, all characters in the extension
1914  * itself are considered literally.
1915  * XXX do we want to consider space as a separator as well ?
1916  * XXX do we want to consider the separators in non-patterns as well ?
1917  */
1918
1919 /*!
1920  * \brief helper functions to sort extension patterns in the desired way,
1921  * so that more specific patterns appear first.
1922  *
1923  * \details
1924  * The function compares individual characters (or sets of), returning
1925  * an int where bits 0-7 are the ASCII code of the first char in the set,
1926  * bits 8-15 are the number of characters in the set, and bits 16-20 are
1927  * for special cases.
1928  * This way more specific patterns (smaller character sets) appear first.
1929  * Wildcards have a special value, so that we can directly compare them to
1930  * sets by subtracting the two values. In particular:
1931  *  0x001xx     one character, character set starting with xx
1932  *  0x0yyxx     yy characters, character set starting with xx
1933  *  0x18000     '.' (one or more of anything)
1934  *  0x28000     '!' (zero or more of anything)
1935  *  0x30000     NUL (end of string)
1936  *  0x40000     error in set.
1937  * The pointer to the string is advanced according to needs.
1938  * NOTES:
1939  *  1. the empty set is ignored.
1940  *  2. given that a full set has always 0 as the first element,
1941  *     we could encode the special cases as 0xffXX where XX
1942  *     is 1, 2, 3, 4 as used above.
1943  */
1944 static int ext_cmp_pattern_pos(const char **p, unsigned char *bitwise)
1945 {
1946 #define BITS_PER        8       /* Number of bits per unit (byte). */
1947         unsigned char c;
1948         unsigned char cmin;
1949         int count;
1950         const char *end;
1951
1952         do {
1953                 /* Get character and advance. (Ignore '-' chars as eye candy fluff.) */
1954                 do {
1955                         c = *(*p)++;
1956                 } while (c == '-');
1957
1958                 /* always return unless we have a set of chars */
1959                 switch (c) {
1960                 default:
1961                         /* ordinary character */
1962                         bitwise[c / BITS_PER] = 1 << ((BITS_PER - 1) - (c % BITS_PER));
1963                         return 0x0100 | c;
1964
1965                 case 'n':
1966                 case 'N':
1967                         /* 2..9 */
1968                         bitwise[6] = 0x3f;
1969                         bitwise[7] = 0xc0;
1970                         return 0x0800 | '2';
1971
1972                 case 'x':
1973                 case 'X':
1974                         /* 0..9 */
1975                         bitwise[6] = 0xff;
1976                         bitwise[7] = 0xc0;
1977                         return 0x0A00 | '0';
1978
1979                 case 'z':
1980                 case 'Z':
1981                         /* 1..9 */
1982                         bitwise[6] = 0x7f;
1983                         bitwise[7] = 0xc0;
1984                         return 0x0900 | '1';
1985
1986                 case '.':
1987                         /* wildcard */
1988                         return 0x18000;
1989
1990                 case '!':
1991                         /* earlymatch */
1992                         return 0x28000; /* less specific than '.' */
1993
1994                 case '\0':
1995                         /* empty string */
1996                         *p = NULL;
1997                         return 0x30000;
1998
1999                 case '[':
2000                         /* char set */
2001                         break;
2002                 }
2003                 /* locate end of set */
2004                 end = strchr(*p, ']');
2005
2006                 if (!end) {
2007                         ast_log(LOG_WARNING, "Wrong usage of [] in the extension\n");
2008                         return 0x40000; /* XXX make this entry go last... */
2009                 }
2010
2011                 count = 0;
2012                 cmin = 0xFF;
2013                 for (; *p < end; ++*p) {
2014                         unsigned char c1;       /* first char in range */
2015                         unsigned char c2;       /* last char in range */
2016
2017                         c1 = (*p)[0];
2018                         if (*p + 2 < end && (*p)[1] == '-') { /* this is a range */
2019                                 c2 = (*p)[2];
2020                                 *p += 2;    /* skip a total of 3 chars */
2021                         } else {        /* individual character */
2022                                 c2 = c1;
2023                         }
2024                         if (c1 < cmin) {
2025                                 cmin = c1;
2026                         }
2027                         for (; c1 <= c2; ++c1) {
2028                                 unsigned char mask = 1 << ((BITS_PER - 1) - (c1 % BITS_PER));
2029
2030                                 /*
2031                                  * Note: If two character sets score the same, the one with the
2032                                  * lowest ASCII values will compare as coming first.  Must fill
2033                                  * in most significant bits for lower ASCII values to accomplish
2034                                  * the desired sort order.
2035                                  */
2036                                 if (!(bitwise[c1 / BITS_PER] & mask)) {
2037                                         /* Add the character to the set. */
2038                                         bitwise[c1 / BITS_PER] |= mask;
2039                                         count += 0x100;
2040                                 }
2041                         }
2042                 }
2043                 ++*p;
2044         } while (!count);/* While the char set was empty. */
2045         return count | cmin;
2046 }
2047
2048 /*!
2049  * \internal
2050  * \brief Comparison of exten patterns.
2051  *
2052  * \param left Pattern to compare.
2053  * \param right Pattern to compare.
2054  *
2055  * \retval <0 if left < right
2056  * \retval =0 if left == right
2057  * \retval >0 if left > right
2058  */
2059 static int ext_cmp_pattern(const char *left, const char *right)
2060 {
2061         int cmp;
2062         int left_pos;
2063         int right_pos;
2064
2065         for (;;) {
2066                 unsigned char left_bitwise[32] = { 0, };
2067                 unsigned char right_bitwise[32] = { 0, };
2068
2069                 left_pos = ext_cmp_pattern_pos(&left, left_bitwise);
2070                 right_pos = ext_cmp_pattern_pos(&right, right_bitwise);
2071                 cmp = left_pos - right_pos;
2072                 if (!cmp) {
2073                         /*
2074                          * Are the character sets different, even though they score the same?
2075                          *
2076                          * Note: Must swap left and right to get the sense of the
2077                          * comparison correct.  Otherwise, we would need to multiply by
2078                          * -1 instead.
2079                          */
2080                         cmp = memcmp(right_bitwise, left_bitwise, ARRAY_LEN(left_bitwise));
2081                 }
2082                 if (cmp) {
2083                         break;
2084                 }
2085                 if (!left) {
2086                         /*
2087                          * Get here only if both patterns ended at the same time.  cmp
2088                          * would be non-zero if only one pattern ended.
2089                          */
2090                         break;
2091                 }
2092         }
2093         return cmp;
2094 }
2095
2096 /*!
2097  * \internal
2098  * \brief Comparison of dialplan extens for sorting purposes.
2099  *
2100  * \param left Exten/pattern to compare.
2101  * \param right Exten/pattern to compare.
2102  *
2103  * \retval <0 if left < right
2104  * \retval =0 if left == right
2105  * \retval >0 if left > right
2106  */
2107 static int ext_cmp(const char *left, const char *right)
2108 {
2109         /* Make sure non-pattern extens come first. */
2110         if (left[0] != '_') {
2111                 if (right[0] == '_') {
2112                         return -1;
2113                 }
2114                 /* Compare two non-pattern extens. */
2115                 return ext_cmp_exten(left, right);
2116         }
2117         if (right[0] != '_') {
2118                 return 1;
2119         }
2120
2121         /*
2122          * OK, we need full pattern sorting routine.
2123          *
2124          * Skip past the underscores
2125          */
2126         return ext_cmp_pattern(left + 1, right + 1);
2127 }
2128
2129 static int ext_fluff_count(const char *exten)
2130 {
2131         int fluff = 0;
2132
2133         if (*exten != '_') {
2134                 /* not a pattern, simple check. */
2135                 while (*exten) {
2136                         if (*exten == '-') {
2137                                 fluff++;
2138                         }
2139                         exten++;
2140                 }
2141
2142                 return fluff;
2143         }
2144
2145         /* do pattern check */
2146         while (*exten) {
2147                 if (*exten == '-') {
2148                         fluff++;
2149                 } else if (*exten == '[') {
2150                         /* skip set, dashes here matter. */
2151                         exten = strchr(exten, ']');
2152
2153                         if (!exten) {
2154                                 /* we'll end up warning about this later, don't spam logs */
2155                                 return fluff;
2156                         }
2157                 }
2158                 exten++;
2159         }
2160
2161         return fluff;
2162 }
2163
2164 int ast_extension_cmp(const char *a, const char *b)
2165 {
2166         int cmp;
2167
2168         cmp = ext_cmp(a, b);
2169         if (cmp < 0) {
2170                 return -1;
2171         }
2172         if (cmp > 0) {
2173                 return 1;
2174         }
2175         return 0;
2176 }
2177
2178 /*!
2179  * \internal
2180  * \brief used ast_extension_{match|close}
2181  * mode is as follows:
2182  *      E_MATCH         success only on exact match
2183  *      E_MATCHMORE     success only on partial match (i.e. leftover digits in pattern)
2184  *      E_CANMATCH      either of the above.
2185  * \retval 0 on no-match
2186  * \retval 1 on match
2187  * \retval 2 on early match.
2188  */
2189
2190 static int _extension_match_core(const char *pattern, const char *data, enum ext_match_t mode)
2191 {
2192         mode &= E_MATCH_MASK;   /* only consider the relevant bits */
2193
2194 #ifdef NEED_DEBUG_HERE
2195         ast_log(LOG_NOTICE,"match core: pat: '%s', dat: '%s', mode=%d\n", pattern, data, (int)mode);
2196 #endif
2197
2198         if (pattern[0] != '_') { /* not a pattern, try exact or partial match */
2199                 int lp = ext_cmp_exten_strlen(pattern);
2200                 int ld = ext_cmp_exten_strlen(data);
2201
2202                 if (lp < ld) {          /* pattern too short, cannot match */
2203 #ifdef NEED_DEBUG_HERE
2204                         ast_log(LOG_NOTICE,"return (0) - pattern too short, cannot match\n");
2205 #endif
2206                         return 0;
2207                 }
2208                 /* depending on the mode, accept full or partial match or both */
2209                 if (mode == E_MATCH) {
2210 #ifdef NEED_DEBUG_HERE
2211                         ast_log(LOG_NOTICE,"return (!ext_cmp_exten(%s,%s) when mode== E_MATCH)\n", pattern, data);
2212 #endif
2213                         return !ext_cmp_exten(pattern, data); /* 1 on match, 0 on fail */
2214                 }
2215                 if (ld == 0 || !ext_cmp_exten_partial(pattern, data)) { /* partial or full match */
2216 #ifdef NEED_DEBUG_HERE
2217                         ast_log(LOG_NOTICE,"return (mode(%d) == E_MATCHMORE ? lp(%d) > ld(%d) : 1)\n", mode, lp, ld);
2218 #endif
2219                         return (mode == E_MATCHMORE) ? lp > ld : 1; /* XXX should consider '!' and '/' ? */
2220                 } else {
2221 #ifdef NEED_DEBUG_HERE
2222                         ast_log(LOG_NOTICE,"return (0) when ld(%d) > 0 && pattern(%s) != data(%s)\n", ld, pattern, data);
2223 #endif
2224                         return 0;
2225                 }
2226         }
2227         if (mode == E_MATCH && data[0] == '_') {
2228                 /*
2229                  * XXX It is bad design that we don't know if we should be
2230                  * comparing data and pattern as patterns or comparing data if
2231                  * it conforms to pattern when the function is called.  First,
2232                  * assume they are both patterns.  If they don't match then try
2233                  * to see if data conforms to the given pattern.
2234                  *
2235                  * note: if this test is left out, then _x. will not match _x. !!!
2236                  */
2237 #ifdef NEED_DEBUG_HERE
2238                 ast_log(LOG_NOTICE, "Comparing as patterns first. pattern:%s data:%s\n", pattern, data);
2239 #endif
2240                 if (!ext_cmp_pattern(pattern + 1, data + 1)) {
2241 #ifdef NEED_DEBUG_HERE
2242                         ast_log(LOG_NOTICE,"return (1) - pattern matches pattern\n");
2243 #endif
2244                         return 1;
2245                 }
2246         }
2247
2248         ++pattern; /* skip leading _ */
2249         /*
2250          * XXX below we stop at '/' which is a separator for the CID info. However we should
2251          * not store '/' in the pattern at all. When we insure it, we can remove the checks.
2252          */
2253         for (;;) {
2254                 const char *end;
2255
2256                 /* Ignore '-' chars as eye candy fluff. */
2257                 while (*data == '-') {
2258                         ++data;
2259                 }
2260                 while (*pattern == '-') {
2261                         ++pattern;
2262                 }
2263                 if (!*data || !*pattern || *pattern == '/') {
2264                         break;
2265                 }
2266
2267                 switch (*pattern) {
2268                 case '[':       /* a range */
2269                         ++pattern;
2270                         end = strchr(pattern, ']'); /* XXX should deal with escapes ? */
2271                         if (!end) {
2272                                 ast_log(LOG_WARNING, "Wrong usage of [] in the extension\n");
2273                                 return 0;       /* unconditional failure */
2274                         }
2275                         if (pattern == end) {
2276                                 /* Ignore empty character sets. */
2277                                 ++pattern;
2278                                 continue;
2279                         }
2280                         for (; pattern < end; ++pattern) {
2281                                 if (pattern+2 < end && pattern[1] == '-') { /* this is a range */
2282                                         if (*data >= pattern[0] && *data <= pattern[2])
2283                                                 break;  /* match found */
2284                                         else {
2285                                                 pattern += 2; /* skip a total of 3 chars */
2286                                                 continue;
2287                                         }
2288                                 } else if (*data == pattern[0])
2289                                         break;  /* match found */
2290                         }
2291                         if (pattern >= end) {
2292 #ifdef NEED_DEBUG_HERE
2293                                 ast_log(LOG_NOTICE,"return (0) when pattern>=end\n");
2294 #endif
2295                                 return 0;
2296                         }
2297                         pattern = end;  /* skip and continue */
2298                         break;
2299                 case 'n':
2300                 case 'N':
2301                         if (*data < '2' || *data > '9') {
2302 #ifdef NEED_DEBUG_HERE
2303                                 ast_log(LOG_NOTICE,"return (0) N is not matched\n");
2304 #endif
2305                                 return 0;
2306                         }
2307                         break;
2308                 case 'x':
2309                 case 'X':
2310                         if (*data < '0' || *data > '9') {
2311 #ifdef NEED_DEBUG_HERE
2312                                 ast_log(LOG_NOTICE,"return (0) X is not matched\n");
2313 #endif
2314                                 return 0;
2315                         }
2316                         break;
2317                 case 'z':
2318                 case 'Z':
2319                         if (*data < '1' || *data > '9') {
2320 #ifdef NEED_DEBUG_HERE
2321                                 ast_log(LOG_NOTICE,"return (0) Z is not matched\n");
2322 #endif
2323                                 return 0;
2324                         }
2325                         break;
2326                 case '.':       /* Must match, even with more digits */
2327 #ifdef NEED_DEBUG_HERE
2328                         ast_log(LOG_NOTICE, "return (1) when '.' is matched\n");
2329 #endif
2330                         return 1;
2331                 case '!':       /* Early match */
2332 #ifdef NEED_DEBUG_HERE
2333                         ast_log(LOG_NOTICE, "return (2) when '!' is matched\n");
2334 #endif
2335                         return 2;
2336                 default:
2337                         if (*data != *pattern) {
2338 #ifdef NEED_DEBUG_HERE
2339                                 ast_log(LOG_NOTICE, "return (0) when *data(%c) != *pattern(%c)\n", *data, *pattern);
2340 #endif
2341                                 return 0;
2342                         }
2343                         break;
2344                 }
2345                 ++data;
2346                 ++pattern;
2347         }
2348         if (*data)                      /* data longer than pattern, no match */ {
2349 #ifdef NEED_DEBUG_HERE
2350                 ast_log(LOG_NOTICE, "return (0) when data longer than pattern\n");
2351 #endif
2352                 return 0;
2353         }
2354
2355         /*
2356          * match so far, but ran off the end of data.
2357          * Depending on what is next, determine match or not.
2358          */
2359         if (*pattern == '\0' || *pattern == '/') {      /* exact match */
2360 #ifdef NEED_DEBUG_HERE
2361                 ast_log(LOG_NOTICE, "at end, return (%d) in 'exact match'\n", (mode==E_MATCHMORE) ? 0 : 1);
2362 #endif
2363                 return (mode == E_MATCHMORE) ? 0 : 1;   /* this is a failure for E_MATCHMORE */
2364         } else if (*pattern == '!')     {               /* early match */
2365 #ifdef NEED_DEBUG_HERE
2366                 ast_log(LOG_NOTICE, "at end, return (2) when '!' is matched\n");
2367 #endif
2368                 return 2;
2369         } else {                                                /* partial match */
2370 #ifdef NEED_DEBUG_HERE
2371                 ast_log(LOG_NOTICE, "at end, return (%d) which deps on E_MATCH\n", (mode == E_MATCH) ? 0 : 1);
2372 #endif
2373                 return (mode == E_MATCH) ? 0 : 1;       /* this is a failure for E_MATCH */
2374         }
2375 }
2376
2377 /*
2378  * Wrapper around _extension_match_core() to do performance measurement
2379  * using the profiling code.
2380  */
2381 static int extension_match_core(const char *pattern, const char *data, enum ext_match_t mode)
2382 {
2383         int i;
2384         static int prof_id = -2;        /* marker for 'unallocated' id */
2385         if (prof_id == -2) {
2386                 prof_id = ast_add_profile("ext_match", 0);
2387         }
2388         ast_mark(prof_id, 1);
2389         i = _extension_match_core(ast_strlen_zero(pattern) ? "" : pattern, ast_strlen_zero(data) ? "" : data, mode);
2390         ast_mark(prof_id, 0);
2391         return i;
2392 }
2393
2394 int ast_extension_match(const char *pattern, const char *data)
2395 {
2396         return extension_match_core(pattern, data, E_MATCH);
2397 }
2398
2399 int ast_extension_close(const char *pattern, const char *data, int needmore)
2400 {
2401         if (needmore != E_MATCHMORE && needmore != E_CANMATCH)
2402                 ast_log(LOG_WARNING, "invalid argument %d\n", needmore);
2403         return extension_match_core(pattern, data, needmore);
2404 }
2405
2406 /* This structure must remain in sync with ast_context for proper hashtab matching */
2407 struct fake_context /* this struct is purely for matching in the hashtab */
2408 {
2409         ast_rwlock_t lock;
2410         struct ast_exten *root;
2411         struct ast_hashtab *root_table;
2412         struct match_char *pattern_tree;
2413         struct ast_context *next;
2414         struct ast_includes includes;
2415         struct ast_ignorepats ignorepats;
2416         struct ast_sws alts;
2417         const char *registrar;
2418         int refcount;
2419         int autohints;
2420         ast_mutex_t macrolock;
2421         char name[256];
2422 };
2423
2424 struct ast_context *ast_context_find(const char *name)
2425 {
2426         struct ast_context *tmp;
2427         struct fake_context item;
2428
2429         if (!name) {
2430                 return NULL;
2431         }
2432         ast_rdlock_contexts();
2433         if (contexts_table) {
2434                 ast_copy_string(item.name, name, sizeof(item.name));
2435                 tmp = ast_hashtab_lookup(contexts_table, &item);
2436         } else {
2437                 tmp = NULL;
2438                 while ((tmp = ast_walk_contexts(tmp))) {
2439                         if (!strcasecmp(name, tmp->name)) {
2440                                 break;
2441                         }
2442                 }
2443         }
2444         ast_unlock_contexts();
2445         return tmp;
2446 }
2447
2448 #define STATUS_NO_CONTEXT       1
2449 #define STATUS_NO_EXTENSION     2
2450 #define STATUS_NO_PRIORITY      3
2451 #define STATUS_NO_LABEL         4
2452 #define STATUS_SUCCESS          5
2453
2454 static int matchcid(const char *cidpattern, const char *callerid)
2455 {
2456         /* If the Caller*ID pattern is empty, then we're matching NO Caller*ID, so
2457            failing to get a number should count as a match, otherwise not */
2458
2459         if (ast_strlen_zero(callerid)) {
2460                 return ast_strlen_zero(cidpattern) ? 1 : 0;
2461         }
2462
2463         return ast_extension_match(cidpattern, callerid);
2464 }
2465
2466 struct ast_exten *pbx_find_extension(struct ast_channel *chan,
2467         struct ast_context *bypass, struct pbx_find_info *q,
2468         const char *context, const char *exten, int priority,
2469         const char *label, const char *callerid, enum ext_match_t action)
2470 {
2471         int x, res;
2472         struct ast_context *tmp = NULL;
2473         struct ast_exten *e = NULL, *eroot = NULL;
2474         struct ast_exten pattern = {NULL, };
2475         struct scoreboard score = {0, };
2476         struct ast_str *tmpdata = NULL;
2477         int idx;
2478
2479         pattern.label = label;
2480         pattern.priority = priority;
2481 #ifdef NEED_DEBUG_HERE
2482         ast_log(LOG_NOTICE, "Looking for cont/ext/prio/label/action = %s/%s/%d/%s/%d\n", context, exten, priority, label, (int) action);
2483 #endif
2484
2485         /* Initialize status if appropriate */
2486         if (q->stacklen == 0) {
2487                 q->status = STATUS_NO_CONTEXT;
2488                 q->swo = NULL;
2489                 q->data = NULL;
2490                 q->foundcontext = NULL;
2491         } else if (q->stacklen >= AST_PBX_MAX_STACK) {
2492                 ast_log(LOG_WARNING, "Maximum PBX stack exceeded\n");
2493                 return NULL;
2494         }
2495
2496         /* Check first to see if we've already been checked */
2497         for (x = 0; x < q->stacklen; x++) {
2498                 if (!strcasecmp(q->incstack[x], context))
2499                         return NULL;
2500         }
2501
2502         if (bypass) { /* bypass means we only look there */
2503                 tmp = bypass;
2504         } else {      /* look in contexts */
2505                 tmp = find_context(context);
2506                 if (!tmp) {
2507                         return NULL;
2508                 }
2509         }
2510
2511         if (q->status < STATUS_NO_EXTENSION)
2512                 q->status = STATUS_NO_EXTENSION;
2513
2514         /* Do a search for matching extension */
2515
2516         eroot = NULL;
2517         score.total_specificity = 0;
2518         score.exten = 0;
2519         score.total_length = 0;
2520         if (!tmp->pattern_tree && tmp->root_table) {
2521                 create_match_char_tree(tmp);
2522 #ifdef NEED_DEBUG
2523                 ast_debug(1, "Tree Created in context %s:\n", context);
2524                 log_match_char_tree(tmp->pattern_tree," ");
2525 #endif
2526         }
2527 #ifdef NEED_DEBUG
2528         ast_log(LOG_NOTICE, "The Trie we are searching in:\n");
2529         log_match_char_tree(tmp->pattern_tree, "::  ");
2530 #endif
2531
2532         do {
2533                 if (!ast_strlen_zero(overrideswitch)) {
2534                         char *osw = ast_strdupa(overrideswitch), *name;
2535                         struct ast_switch *asw;
2536                         ast_switch_f *aswf = NULL;
2537                         char *datap;
2538                         int eval = 0;
2539
2540                         name = strsep(&osw, "/");
2541                         asw = pbx_findswitch(name);
2542
2543                         if (!asw) {
2544                                 ast_log(LOG_WARNING, "No such switch '%s'\n", name);
2545                                 break;
2546                         }
2547
2548                         if (osw && strchr(osw, '$')) {
2549                                 eval = 1;
2550                         }
2551
2552                         if (eval && !(tmpdata = ast_str_thread_get(&switch_data, 512))) {
2553                                 ast_log(LOG_WARNING, "Can't evaluate overrideswitch?!\n");
2554                                 break;
2555                         } else if (eval) {
2556                                 /* Substitute variables now */
2557                                 pbx_substitute_variables_helper(chan, osw, ast_str_buffer(tmpdata), ast_str_size(tmpdata));
2558                                 datap = ast_str_buffer(tmpdata);
2559                         } else {
2560                                 datap = osw;
2561                         }
2562
2563                         /* equivalent of extension_match_core() at the switch level */
2564                         if (action == E_CANMATCH)
2565                                 aswf = asw->canmatch;
2566                         else if (action == E_MATCHMORE)
2567                                 aswf = asw->matchmore;
2568                         else /* action == E_MATCH */
2569                                 aswf = asw->exists;
2570                         if (!aswf) {
2571                                 res = 0;
2572                         } else {
2573                                 if (chan) {
2574                                         ast_autoservice_start(chan);
2575                                 }
2576                                 res = aswf(chan, context, exten, priority, callerid, datap);
2577                                 if (chan) {
2578                                         ast_autoservice_stop(chan);
2579                                 }
2580                         }
2581                         if (res) {      /* Got a match */
2582                                 q->swo = asw;
2583                                 q->data = datap;
2584                                 q->foundcontext = context;
2585                                 /* XXX keep status = STATUS_NO_CONTEXT ? */
2586                                 return NULL;
2587                         }
2588                 }
2589         } while (0);
2590
2591         if (extenpatternmatchnew) {
2592                 new_find_extension(exten, &score, tmp->pattern_tree, 0, 0, callerid, label, action);
2593                 eroot = score.exten;
2594
2595                 if (score.last_char == '!' && action == E_MATCHMORE) {
2596                         /* We match an extension ending in '!'.
2597                          * The decision in this case is final and is NULL (no match).
2598                          */
2599 #ifdef NEED_DEBUG_HERE
2600                         ast_log(LOG_NOTICE,"Returning MATCHMORE NULL with exclamation point.\n");
2601 #endif
2602                         return NULL;
2603                 }
2604
2605                 if (!eroot && (action == E_CANMATCH || action == E_MATCHMORE) && score.canmatch_exten) {
2606                         q->status = STATUS_SUCCESS;
2607 #ifdef NEED_DEBUG_HERE
2608                         ast_log(LOG_NOTICE,"Returning CANMATCH exten %s\n", score.canmatch_exten->exten);
2609 #endif
2610                         return score.canmatch_exten;
2611                 }
2612
2613                 if ((action == E_MATCHMORE || action == E_CANMATCH)  && eroot) {
2614                         if (score.node) {
2615                                 struct ast_exten *z = trie_find_next_match(score.node);
2616                                 if (z) {
2617 #ifdef NEED_DEBUG_HERE
2618                                         ast_log(LOG_NOTICE,"Returning CANMATCH/MATCHMORE next_match exten %s\n", z->exten);
2619 #endif
2620                                 } else {
2621                                         if (score.canmatch_exten) {
2622 #ifdef NEED_DEBUG_HERE
2623                                                 ast_log(LOG_NOTICE,"Returning CANMATCH/MATCHMORE canmatchmatch exten %s(%p)\n", score.canmatch_exten->exten, score.canmatch_exten);
2624 #endif
2625                                                 return score.canmatch_exten;
2626                                         } else {
2627 #ifdef NEED_DEBUG_HERE
2628                                                 ast_log(LOG_NOTICE,"Returning CANMATCH/MATCHMORE next_match exten NULL\n");
2629 #endif
2630                                         }
2631                                 }
2632                                 return z;
2633                         }
2634 #ifdef NEED_DEBUG_HERE
2635                         ast_log(LOG_NOTICE, "Returning CANMATCH/MATCHMORE NULL (no next_match)\n");
2636 #endif
2637                         return NULL;  /* according to the code, complete matches are null matches in MATCHMORE mode */
2638                 }
2639
2640                 if (eroot) {
2641                         /* found entry, now look for the right priority */
2642                         if (q->status < STATUS_NO_PRIORITY)
2643                                 q->status = STATUS_NO_PRIORITY;
2644                         e = NULL;
2645                         if (action == E_FINDLABEL && label ) {
2646                                 if (q->status < STATUS_NO_LABEL)
2647                                         q->status = STATUS_NO_LABEL;
2648                                 e = ast_hashtab_lookup(eroot->peer_label_table, &pattern);
2649                         } else {
2650                                 e = ast_hashtab_lookup(eroot->peer_table, &pattern);
2651                         }
2652                         if (e) {        /* found a valid match */
2653                                 q->status = STATUS_SUCCESS;
2654                                 q->foundcontext = context;
2655 #ifdef NEED_DEBUG_HERE
2656                                 ast_log(LOG_NOTICE,"Returning complete match of exten %s\n", e->exten);
2657 #endif
2658                                 return e;
2659                         }
2660                 }
2661         } else {   /* the old/current default exten pattern match algorithm */
2662
2663                 /* scan the list trying to match extension and CID */
2664                 eroot = NULL;
2665                 while ( (eroot = ast_walk_context_extensions(tmp, eroot)) ) {
2666                         int match = extension_match_core(eroot->exten, exten, action);
2667                         /* 0 on fail, 1 on match, 2 on earlymatch */
2668
2669                         if (!match || (eroot->matchcid && !matchcid(eroot->cidmatch, callerid)))
2670                                 continue;       /* keep trying */
2671                         if (match == 2 && action == E_MATCHMORE) {
2672                                 /* We match an extension ending in '!'.
2673                                  * The decision in this case is final and is NULL (no match).
2674                                  */
2675                                 return NULL;
2676                         }
2677                         /* found entry, now look for the right priority */
2678                         if (q->status < STATUS_NO_PRIORITY)
2679                                 q->status = STATUS_NO_PRIORITY;
2680                         e = NULL;
2681                         if (action == E_FINDLABEL && label ) {
2682                                 if (q->status < STATUS_NO_LABEL)
2683                                         q->status = STATUS_NO_LABEL;
2684                                 e = ast_hashtab_lookup(eroot->peer_label_table, &pattern);
2685                         } else {
2686                                 e = ast_hashtab_lookup(eroot->peer_table, &pattern);
2687                         }
2688                         if (e) {        /* found a valid match */
2689                                 q->status = STATUS_SUCCESS;
2690                                 q->foundcontext = context;
2691                                 return e;
2692                         }
2693                 }
2694         }
2695
2696         /* Check alternative switches */
2697         for (idx = 0; idx < ast_context_switches_count(tmp); idx++) {
2698                 const struct ast_sw *sw = ast_context_switches_get(tmp, idx);
2699                 struct ast_switch *asw = pbx_findswitch(ast_get_switch_name(sw));
2700                 ast_switch_f *aswf = NULL;
2701                 const char *datap;
2702
2703                 if (!asw) {
2704                         ast_log(LOG_WARNING, "No such switch '%s'\n", ast_get_switch_name(sw));
2705                         continue;
2706                 }
2707
2708                 /* Substitute variables now */
2709                 if (ast_get_switch_eval(sw)) {
2710                         if (!(tmpdata = ast_str_thread_get(&switch_data, 512))) {
2711                                 ast_log(LOG_WARNING, "Can't evaluate switch?!\n");
2712                                 continue;
2713                         }
2714                         pbx_substitute_variables_helper(chan, ast_get_switch_data(sw),
2715                                 ast_str_buffer(tmpdata), ast_str_size(tmpdata));
2716                         datap = ast_str_buffer(tmpdata);
2717                 } else {
2718                         datap = ast_get_switch_data(sw);
2719                 }
2720
2721                 /* equivalent of extension_match_core() at the switch level */
2722                 if (action == E_CANMATCH)
2723                         aswf = asw->canmatch;
2724                 else if (action == E_MATCHMORE)
2725                         aswf = asw->matchmore;
2726                 else /* action == E_MATCH */
2727                         aswf = asw->exists;
2728                 if (!aswf)
2729                         res = 0;
2730                 else {
2731                         if (chan)
2732                                 ast_autoservice_start(chan);
2733                         res = aswf(chan, context, exten, priority, callerid, datap);
2734                         if (chan)
2735                                 ast_autoservice_stop(chan);
2736                 }
2737                 if (res) {      /* Got a match */
2738                         q->swo = asw;
2739                         q->data = datap;
2740                         q->foundcontext = context;
2741                         /* XXX keep status = STATUS_NO_CONTEXT ? */
2742                         return NULL;
2743                 }
2744         }
2745         q->incstack[q->stacklen++] = tmp->name; /* Setup the stack */
2746         /* Now try any includes we have in this context */
2747         for (idx = 0; idx < ast_context_includes_count(tmp); idx++) {
2748                 const struct ast_include *i = ast_context_includes_get(tmp, idx);
2749
2750                 if (include_valid(i)) {
2751                         if ((e = pbx_find_extension(chan, bypass, q, include_rname(i), exten, priority, label, callerid, action))) {
2752 #ifdef NEED_DEBUG_HERE
2753                                 ast_log(LOG_NOTICE,"Returning recursive match of %s\n", e->exten);
2754 #endif
2755                                 return e;
2756                         }
2757                         if (q->swo)
2758                                 return NULL;
2759                 }
2760         }
2761         return NULL;
2762 }
2763
2764 static void exception_store_free(void *data)
2765 {
2766         struct pbx_exception *exception = data;
2767         ast_string_field_free_memory(exception);
2768         ast_free(exception);
2769 }
2770
2771 static const struct ast_datastore_info exception_store_info = {
2772         .type = "EXCEPTION",
2773         .destroy = exception_store_free,
2774 };
2775
2776 /*!
2777  * \internal
2778  * \brief Set the PBX to execute the exception extension.
2779  *
2780  * \param chan Channel to raise the exception on.
2781  * \param reason Reason exception is raised.
2782  * \param priority Dialplan priority to set.
2783  *
2784  * \retval 0 on success.
2785  * \retval -1 on error.
2786  */
2787 int raise_exception(struct ast_channel *chan, const char *reason, int priority)
2788 {
2789         struct ast_datastore *ds = ast_channel_datastore_find(chan, &exception_store_info, NULL);
2790         struct pbx_exception *exception = NULL;
2791
2792         if (!ds) {
2793                 ds = ast_datastore_alloc(&exception_store_info, NULL);
2794                 if (!ds)
2795                         return -1;
2796                 if (!(exception = ast_calloc_with_stringfields(1, struct pbx_exception, 128))) {
2797                         ast_datastore_free(ds);
2798                         return -1;
2799                 }
2800                 ds->data = exception;
2801                 ast_channel_datastore_add(chan, ds);
2802         } else
2803                 exception = ds->data;
2804
2805         ast_string_field_set(exception, reason, reason);
2806         ast_string_field_set(exception, context, ast_channel_context(chan));
2807         ast_string_field_set(exception, exten, ast_channel_exten(chan));
2808         exception->priority = ast_channel_priority(chan);
2809         set_ext_pri(chan, "e", priority);
2810         return 0;
2811 }
2812
2813 static int acf_exception_read(struct ast_channel *chan, const char *name, char *data, char *buf, size_t buflen)
2814 {
2815         struct ast_datastore *ds = ast_channel_datastore_find(chan, &exception_store_info, NULL);
2816         struct pbx_exception *exception = NULL;
2817         if (!ds || !ds->data)
2818                 return -1;
2819         exception = ds->data;
2820         if (!strcasecmp(data, "REASON"))
2821                 ast_copy_string(buf, exception->reason, buflen);
2822         else if (!strcasecmp(data, "CONTEXT"))
2823                 ast_copy_string(buf, exception->context, buflen);
2824         else if (!strncasecmp(data, "EXTEN", 5))
2825                 ast_copy_string(buf, exception->exten, buflen);
2826         else if (!strcasecmp(data, "PRIORITY"))
2827                 snprintf(buf, buflen, "%d", exception->priority);
2828         else
2829                 return -1;
2830         return 0;
2831 }
2832
2833 static struct ast_custom_function exception_function = {
2834         .name = "EXCEPTION",
2835         .read = acf_exception_read,
2836 };
2837
2838 /*!
2839  * \brief The return value depends on the action:
2840  *
2841  * E_MATCH, E_CANMATCH, E_MATCHMORE require a real match,
2842  *      and return 0 on failure, -1 on match;
2843  * E_FINDLABEL maps the label to a priority, and returns
2844  *      the priority on success, ... XXX
2845  * E_SPAWN, spawn an application,
2846  *
2847  * \retval 0 on success.
2848  * \retval  -1 on failure.
2849  *
2850  * \note The channel is auto-serviced in this function, because doing an extension
2851  * match may block for a long time.  For example, if the lookup has to use a network
2852  * dialplan switch, such as DUNDi or IAX2, it may take a while.  However, the channel
2853  * auto-service code will queue up any important signalling frames to be processed
2854  * after this is done.
2855  */
2856 static int pbx_extension_helper(struct ast_channel *c, struct ast_context *con,
2857   const char *context, const char *exten, int priority,
2858   const char *label, const char *callerid, enum ext_match_t action, int *found, int combined_find_spawn)
2859 {
2860         struct ast_exten *e;
2861         struct ast_app *app;
2862         char *substitute = NULL;
2863         int res;
2864         struct pbx_find_info q = { .stacklen = 0 }; /* the rest is reset in pbx_find_extension */
2865         char passdata[EXT_DATA_SIZE];
2866         int matching_action = (action == E_MATCH || action == E_CANMATCH || action == E_MATCHMORE);
2867
2868         ast_rdlock_contexts();
2869         if (found)
2870                 *found = 0;
2871
2872         e = pbx_find_extension(c, con, &q, context, exten, priority, label, callerid, action);
2873         if (e) {
2874                 if (found)
2875                         *found = 1;
2876                 if (matching_action) {
2877                         ast_unlock_contexts();
2878                         return -1;      /* success, we found it */
2879                 } else if (action == E_FINDLABEL) { /* map the label to a priority */
2880                         res = e->priority;
2881                         ast_unlock_contexts();
2882                         return res;     /* the priority we were looking for */
2883                 } else {        /* spawn */
2884                         if (!e->cached_app)
2885                                 e->cached_app = pbx_findapp(e->app);
2886                         app = e->cached_app;
2887                         if (ast_strlen_zero(e->data)) {
2888                                 *passdata = '\0';
2889                         } else {
2890                                 const char *tmp;
2891                                 if ((!(tmp = strchr(e->data, '$'))) || (!strstr(tmp, "${") && !strstr(tmp, "$["))) {
2892                                         /* no variables to substitute, copy on through */
2893                                         ast_copy_string(passdata, e->data, sizeof(passdata));
2894                                 } else {
2895                                         /* save e->data on stack for later processing after lock released */
2896                                         substitute = ast_strdupa(e->data);
2897                                 }
2898                         }
2899                         ast_unlock_contexts();
2900                         if (!app) {
2901                                 ast_log(LOG_WARNING, "No application '%s' for extension (%s, %s, %d)\n", e->app, context, exten, priority);
2902                                 return -1;
2903                         }
2904                         if (ast_channel_context(c) != context)
2905                                 ast_channel_context_set(c, context);
2906                         if (ast_channel_exten(c) != exten)
2907                                 ast_channel_exten_set(c, exten);
2908                         ast_channel_priority_set(c, priority);
2909                         if (substitute) {
2910                                 pbx_substitute_variables_helper(c, substitute, passdata, sizeof(passdata)-1);
2911                         }
2912                         ast_debug(1, "Launching '%s'\n", app_name(app));
2913                         if (VERBOSITY_ATLEAST(3)) {
2914                                 ast_verb(3, "Executing [%s@%s:%d] " COLORIZE_FMT "(\"" COLORIZE_FMT "\", \"" COLORIZE_FMT "\") %s\n",
2915                                         exten, context, priority,
2916                                         COLORIZE(COLOR_BRCYAN, 0, app_name(app)),
2917                                         COLORIZE(COLOR_BRMAGENTA, 0, ast_channel_name(c)),
2918                                         COLORIZE(COLOR_BRMAGENTA, 0, passdata),
2919                                         "in new stack");
2920                         }
2921                         return pbx_exec(c, app, passdata);      /* 0 on success, -1 on failure */
2922                 }
2923         } else if (q.swo) {     /* not found here, but in another switch */
2924                 if (found)
2925                         *found = 1;
2926                 ast_unlock_contexts();
2927                 if (matching_action) {
2928                         return -1;
2929                 } else {
2930                         if (!q.swo->exec) {
2931                                 ast_log(LOG_WARNING, "No execution engine for switch %s\n", q.swo->name);
2932                                 res = -1;
2933                         }
2934                         return q.swo->exec(c, q.foundcontext ? q.foundcontext : context, exten, priority, callerid, q.data);
2935                 }
2936         } else {        /* not found anywhere, see what happened */
2937                 ast_unlock_contexts();
2938                 /* Using S_OR here because Solaris doesn't like NULL being passed to ast_log */
2939                 switch (q.status) {
2940                 case STATUS_NO_CONTEXT:
2941                         if (!matching_action && !combined_find_spawn)
2942                                 ast_log(LOG_NOTICE, "Cannot find extension context '%s'\n", S_OR(context, ""));
2943                         break;
2944                 case STATUS_NO_EXTENSION:
2945                         if (!matching_action && !combined_find_spawn)
2946                                 ast_log(LOG_NOTICE, "Cannot find extension '%s' in context '%s'\n", exten, S_OR(context, ""));
2947                         break;
2948                 case STATUS_NO_PRIORITY:
2949                         if (!matching_action && !combined_find_spawn)
2950                                 ast_log(LOG_NOTICE, "No such priority %d in extension '%s' in context '%s'\n", priority, exten, S_OR(context, ""));
2951                         break;
2952                 case STATUS_NO_LABEL:
2953                         if (context && !combined_find_spawn)
2954                                 ast_log(LOG_NOTICE, "No such label '%s' in extension '%s' in context '%s'\n", label, exten, S_OR(context, ""));
2955                         break;
2956                 default:
2957                         ast_debug(1, "Shouldn't happen!\n");
2958                 }
2959
2960                 return (matching_action) ? 0 : -1;
2961         }
2962 }
2963
2964 /*! \brief Find hint for given extension in context */
2965 static struct ast_exten *ast_hint_extension_nolock(struct ast_channel *c, const char *context, const char *exten)
2966 {
2967         struct pbx_find_info q = { .stacklen = 0 }; /* the rest is set in pbx_find_context */
2968         return pbx_find_extension(c, NULL, &q, context, exten, PRIORITY_HINT, NULL, "", E_MATCH);
2969 }
2970
2971 static struct ast_exten *ast_hint_extension(struct ast_channel *c, const char *context, const char *exten)
2972 {
2973         struct ast_exten *e;
2974         ast_rdlock_contexts();
2975         e = ast_hint_extension_nolock(c, context, exten);
2976         ast_unlock_contexts();
2977         return e;
2978 }
2979
2980 enum ast_extension_states ast_devstate_to_extenstate(enum ast_device_state devstate)
2981 {
2982         switch (devstate) {
2983         case AST_DEVICE_ONHOLD:
2984                 return AST_EXTENSION_ONHOLD;
2985         case AST_DEVICE_BUSY:
2986                 return AST_EXTENSION_BUSY;
2987         case AST_DEVICE_UNKNOWN:
2988                 return AST_EXTENSION_NOT_INUSE;
2989         case AST_DEVICE_UNAVAILABLE:
2990         case AST_DEVICE_INVALID:
2991                 return AST_EXTENSION_UNAVAILABLE;
2992         case AST_DEVICE_RINGINUSE:
2993                 return (AST_EXTENSION_INUSE | AST_EXTENSION_RINGING);
2994         case AST_DEVICE_RINGING:
2995                 return AST_EXTENSION_RINGING;
2996         case AST_DEVICE_INUSE:
2997                 return AST_EXTENSION_INUSE;
2998         case AST_DEVICE_NOT_INUSE:
2999                 return AST_EXTENSION_NOT_INUSE;
3000         case AST_DEVICE_TOTAL: /* not a device state, included for completeness */
3001                 break;
3002         }
3003
3004         return AST_EXTENSION_NOT_INUSE;
3005 }
3006
3007 /*!
3008  * \internal
3009  * \brief Parse out the presence portion of the hint string
3010  */
3011 static char *parse_hint_presence(struct ast_str *hint_args)
3012 {
3013         char *copy = ast_strdupa(ast_str_buffer(hint_args));
3014         char *tmp = "";
3015
3016         if ((tmp = strrchr(copy, ','))) {
3017                 *tmp = '\0';
3018                 tmp++;
3019         } else {
3020                 return NULL;
3021         }
3022         ast_str_set(&hint_args, 0, "%s", tmp);
3023         return ast_str_buffer(hint_args);
3024 }
3025
3026 /*!
3027  * \internal
3028  * \brief Parse out the device portion of the hint string
3029  */
3030 static char *parse_hint_device(struct ast_str *hint_args)
3031 {
3032         char *copy = ast_strdupa(ast_str_buffer(hint_args));
3033         char *tmp;
3034
3035         if ((tmp = strrchr(copy, ','))) {
3036                 *tmp = '\0';
3037         }
3038
3039         ast_str_set(&hint_args, 0, "%s", copy);
3040         return ast_str_buffer(hint_args);
3041 }
3042
3043 static void device_state_info_dt(void *obj)
3044 {
3045         struct ast_device_state_info *info = obj;
3046
3047         ao2_cleanup(info->causing_channel);
3048 }
3049
3050 static struct ao2_container *alloc_device_state_info(void)
3051 {
3052         return ao2_container_alloc_options(AO2_ALLOC_OPT_LOCK_NOLOCK, 1, NULL, NULL);
3053 }
3054
3055 static int ast_extension_state3(struct ast_str *hint_app, struct ao2_container *device_state_info)
3056 {
3057         char *cur;
3058         char *rest;
3059         struct ast_devstate_aggregate agg;
3060
3061         /* One or more devices separated with a & character */
3062         rest = parse_hint_device(hint_app);
3063
3064         ast_devstate_aggregate_init(&agg);
3065         while ((cur = strsep(&rest, "&"))) {
3066                 enum ast_device_state state = ast_device_state(cur);
3067
3068                 ast_devstate_aggregate_add(&agg, state);
3069                 if (device_state_info) {
3070                         struct ast_device_state_info *obj;
3071
3072                         obj = ao2_alloc_options(sizeof(*obj) + strlen(cur), device_state_info_dt, AO2_ALLOC_OPT_LOCK_NOLOCK);
3073                         /* if failed we cannot add this device */
3074                         if (obj) {
3075                                 obj->device_state = state;
3076                                 strcpy(obj->device_name, cur);
3077                                 ao2_link(device_state_info, obj);
3078                                 ao2_ref(obj, -1);
3079                         }
3080                 }
3081         }
3082
3083         return ast_devstate_to_extenstate(ast_devstate_aggregate_result(&agg));
3084 }
3085
3086 /*! \brief Check state of extension by using hints */
3087 static int ast_extension_state2(struct ast_exten *e, struct ao2_container *device_state_info)
3088 {
3089         struct ast_str *hint_app = ast_str_thread_get(&extensionstate_buf, 32);
3090
3091         if (!e || !hint_app) {
3092                 return -1;
3093         }
3094
3095         ast_str_set(&hint_app, 0, "%s", ast_get_extension_app(e));
3096         return ast_extension_state3(hint_app, device_state_info);
3097 }
3098
3099 /*! \brief Return extension_state as string */
3100 const char *ast_extension_state2str(int extension_state)
3101 {
3102         int i;
3103
3104         for (i = 0; (i < ARRAY_LEN(extension_states)); i++) {
3105                 if (extension_states[i].extension_state == extension_state)
3106                         return extension_states[i].text;
3107         }
3108         return "Unknown";
3109 }
3110
3111 /*!
3112  * \internal
3113  * \brief Check extension state for an extension by using hint
3114  */
3115 static int internal_extension_state_extended(struct ast_channel *c, const char *context, const char *exten,
3116         struct ao2_container *device_state_info)
3117 {
3118         struct ast_exten *e;
3119
3120         if (!(e = ast_hint_extension(c, context, exten))) {  /* Do we have a hint for this extension ? */
3121                 return -1;                   /* No hint, return -1 */
3122         }
3123
3124         if (e->exten[0] == '_') {
3125                 /* Create this hint on-the-fly */
3126                 ast_add_extension(e->parent->name, 0, exten, e->priority, e->label,
3127                         e->matchcid ? e->cidmatch : NULL, e->app, ast_strdup(e->data), ast_free_ptr,
3128                         e->registrar);
3129                 if (!(e = ast_hint_extension(c, context, exten))) {
3130                         /* Improbable, but not impossible */
3131                         return -1;
3132                 }
3133         }
3134
3135         return ast_extension_state2(e, device_state_info);  /* Check all devices in the hint */
3136 }
3137
3138 /*! \brief Check extension state for an extension by using hint */
3139 int ast_extension_state(struct ast_channel *c, const char *context, const char *exten)
3140 {
3141         return internal_extension_state_extended(c, context, exten, NULL);
3142 }
3143
3144 /*! \brief Check extended extension state for an extension by using hint */
3145 int ast_extension_state_extended(struct ast_channel *c, const char *context, const char *exten,
3146         struct ao2_container **device_state_info)
3147 {
3148         struct ao2_container *container = NULL;
3149         int ret;
3150
3151         if (device_state_info) {
3152                 container = alloc_device_state_info();
3153         }
3154
3155         ret = internal_extension_state_extended(c, context, exten, container);
3156         if (ret < 0 && container) {
3157                 ao2_ref(container, -1);
3158                 container = NULL;
3159         }
3160
3161         if (device_state_info) {
3162                 get_device_state_causing_channels(container);
3163                 *device_state_info = container;
3164         }
3165
3166         return ret;
3167 }
3168
3169 static int extension_presence_state_helper(struct ast_exten *e, char **subtype, char **message)
3170 {
3171         struct ast_str *hint_app = ast_str_thread_get(&extensionstate_buf, 32);
3172         char *presence_provider;
3173         const char *app;
3174
3175         if (!e || !hint_app) {
3176                 return -1;
3177         }
3178
3179         app = ast_get_extension_app(e);
3180         if (ast_strlen_zero(app)) {
3181                 return -1;
3182         }
3183
3184         ast_str_set(&hint_app, 0, "%s", app);
3185         presence_provider = parse_hint_presence(hint_app);
3186
3187         if (ast_strlen_zero(presence_provider)) {
3188                 /* No presence string in the hint */
3189                 return 0;
3190         }
3191
3192         return ast_presence_state(presence_provider, subtype, message);
3193 }
3194
3195 int ast_hint_presence_state(struct ast_channel *c, const char *context, const char *exten, char **subtype, char **message)
3196 {
3197         struct ast_exten *e;
3198
3199         if (!(e = ast_hint_extension(c, context, exten))) {  /* Do we have a hint for this extension ? */
3200                 return -1;                   /* No hint, return -1 */
3201         }
3202
3203         if (e->exten[0] == '_') {
3204                 /* Create this hint on-the-fly */
3205                 ast_add_extension(e->parent->name, 0, exten, e->priority, e->label,
3206                         e->matchcid ? e->cidmatch : NULL, e->app, ast_strdup(e->data), ast_free_ptr,
3207                         e->registrar);
3208                 if (!(e = ast_hint_extension(c, context, exten))) {
3209                         /* Improbable, but not impossible */
3210                         return -1;
3211                 }
3212         }
3213
3214         return extension_presence_state_helper(e, subtype, message);
3215 }
3216
3217 static int execute_state_callback(ast_state_cb_type cb,
3218         const char *context,
3219         const char *exten,
3220         void *data,
3221         enum ast_state_cb_update_reason reason,
3222         struct ast_hint *hint,
3223         struct ao2_container *device_state_info)
3224 {
3225         int res = 0;
3226         struct ast_state_cb_info info = { 0, };
3227
3228         info.reason = reason;
3229
3230         /* Copy over current hint data */
3231         if (hint) {
3232                 ao2_lock(hint);
3233                 info.exten_state = hint->laststate;
3234                 info.device_state_info = device_state_info;
3235                 info.presence_state = hint->last_presence_state;
3236                 if (!(ast_strlen_zero(hint->last_presence_subtype))) {
3237                         info.presence_subtype = ast_strdupa(hint->last_presence_subtype);
3238                 } else {
3239                         info.presence_subtype = "";
3240                 }
3241                 if (!(ast_strlen_zero(hint->last_presence_message))) {
3242                         info.presence_message = ast_strdupa(hint->last_presence_message);
3243                 } else {
3244                         info.presence_message = "";
3245                 }
3246                 ao2_unlock(hint);
3247         } else {
3248                 info.exten_state = AST_EXTENSION_REMOVED;
3249         }
3250
3251         res = cb(context, exten, &info, data);
3252
3253         return res;
3254 }
3255
3256 /*!
3257  * /internal
3258  * /brief Identify a channel for every device which is supposedly responsible for the device state.
3259  *
3260  * Especially when the device is ringing, the oldest ringing channel is chosen.
3261  * For all other cases the first encountered channel in the specific state is chosen.
3262  */
3263 static void get_device_state_causing_channels(struct ao2_container *c)
3264 {
3265         struct ao2_iterator iter;
3266         struct ast_device_state_info *info;
3267         struct ast_channel *chan;
3268
3269         if (!c || !ao2_container_count(c)) {
3270                 return;
3271         }
3272         iter = ao2_iterator_init(c, 0);
3273         for (; (info = ao2_iterator_next(&iter)); ao2_ref(info, -1)) {
3274                 enum ast_channel_state search_state = 0; /* prevent false uninit warning */
3275                 char match[AST_CHANNEL_NAME];
3276                 struct ast_channel_iterator *chan_iter;
3277                 struct timeval chantime = {0, }; /* prevent false uninit warning */
3278
3279                 switch (info->device_state) {
3280                 case AST_DEVICE_RINGING:
3281                 case AST_DEVICE_RINGINUSE:
3282                         /* find ringing channel */
3283                         search_state = AST_STATE_RINGING;
3284                         break;
3285                 case AST_DEVICE_BUSY:
3286                         /* find busy channel */
3287                         search_state = AST_STATE_BUSY;
3288                         break;
3289                 case AST_DEVICE_ONHOLD:
3290                 case AST_DEVICE_INUSE:
3291                         /* find up channel */
3292                         search_state = AST_STATE_UP;
3293                         break;
3294                 case AST_DEVICE_UNKNOWN:
3295                 case AST_DEVICE_NOT_INUSE:
3296                 case AST_DEVICE_INVALID:
3297                 case AST_DEVICE_UNAVAILABLE:
3298                 case AST_DEVICE_TOTAL /* not a state */:
3299                         /* no channels are of interest */
3300                         continue;
3301                 }
3302
3303                 /* iterate over all channels of the device */
3304                 snprintf(match, sizeof(match), "%s-", info->device_name);
3305                 chan_iter = ast_channel_iterator_by_name_new(match, strlen(match));
3306                 for (; (chan = ast_channel_iterator_next(chan_iter)); ast_channel_unref(chan)) {
3307                         ast_channel_lock(chan);
3308                         /* this channel's state doesn't match */
3309                         if (search_state != ast_channel_state(chan)) {
3310                                 ast_channel_unlock(chan);
3311                                 continue;
3312                         }
3313                         /* any non-ringing channel will fit */
3314                         if (search_state != AST_STATE_RINGING) {
3315                                 ast_channel_unlock(chan);
3316                                 info->causing_channel = chan; /* is kept ref'd! */
3317                                 break;
3318                         }
3319                         /* but we need the oldest ringing channel of the device to match with undirected pickup */
3320                         if (!info->causing_channel) {
3321                                 chantime = ast_channel_creationtime(chan);
3322                                 ast_channel_ref(chan); /* must ref it! */
3323                                 info->causing_channel = chan;
3324                         } else if (ast_tvcmp(ast_channel_creationtime(chan), chantime) < 0) {
3325                                 chantime = ast_channel_creationtime(chan);
3326                                 ast_channel_unref(info->causing_channel);
3327                                 ast_channel_ref(chan); /* must ref it! */
3328                                 info->causing_channel = chan;
3329                         }
3330                         ast_channel_unlock(chan);
3331                 }
3332                 ast_channel_iterator_destroy(chan_iter);
3333         }
3334         ao2_iterator_destroy(&iter);
3335 }
3336
3337 static void device_state_notify_callbacks(struct ast_hint *hint, struct ast_str **hint_app)
3338 {
3339         struct ao2_iterator cb_iter;
3340         struct ast_state_cb *state_cb;
3341         int state;
3342         int same_state;
3343         struct ao2_container *device_state_info;
3344         int first_extended_cb_call = 1;
3345         char context_name[AST_MAX_CONTEXT];
3346         char exten_name[AST_MAX_EXTENSION];
3347
3348         ao2_lock(hint);
3349         if (!hint->exten) {
3350                 /* The extension has already been destroyed */
3351                 ao2_unlock(hint);
3352                 return;
3353         }
3354
3355         /*
3356          * Save off strings in case the hint extension gets destroyed
3357          * while we are notifying the watchers.
3358          */
3359         ast_copy_string(context_name,
3360                         ast_get_context_name(ast_get_extension_context(hint->exten)),
3361                         sizeof(context_name));
3362         ast_copy_string(exten_name, ast_get_extension_name(hint->exten),
3363                         sizeof(exten_name));
3364         ast_str_set(hint_app, 0, "%s", ast_get_extension_app(hint->exten));
3365         ao2_unlock(hint);
3366
3367         /*
3368          * Get device state for this hint.
3369          *
3370          * NOTE: We cannot hold any locks while determining the hint
3371          * device state or notifying the watchers without causing a
3372          * deadlock.  (conlock, hints, and hint)
3373          */
3374
3375         /* Make a container so state3 can fill it if we wish.
3376          * If that failed we simply do not provide the extended state info.
3377          */
3378         device_state_info = alloc_device_state_info();
3379
3380         state = ast_extension_state3(*hint_app, device_state_info);
3381         same_state = state == hint->laststate;
3382         if (same_state && (~state & AST_EXTENSION_RINGING)) {
3383                 ao2_cleanup(device_state_info);
3384                 return;
3385         }
3386
3387         /* Device state changed since last check - notify the watchers. */
3388         hint->laststate = state;        /* record we saw the change */
3389
3390         /* For general callbacks */
3391         if (!same_state) {
3392                 cb_iter = ao2_iterator_init(statecbs, 0);
3393                 for (; (state_cb = ao2_iterator_next(&cb_iter)); ao2_ref(state_cb, -1)) {
3394                         execute_state_callback(state_cb->change_cb,
3395                                 context_name,
3396                                 exten_name,
3397                                 state_cb->data,
3398                                 AST_HINT_UPDATE_DEVICE,
3399                                 hint,
3400                                 NULL);
3401                 }
3402                 ao2_iterator_destroy(&cb_iter);
3403         }
3404
3405         /* For extension callbacks */
3406         /* extended callbacks are called when the state changed or when AST_STATE_RINGING is
3407          * included. Normal callbacks are only called when the state changed.
3408          */
3409         cb_iter = ao2_iterator_init(hint->callbacks, 0);
3410         for (; (state_cb = ao2_iterator_next(&cb_iter)); ao2_ref(state_cb, -1)) {
3411                 if (state_cb->extended && first_extended_cb_call) {
3412                         /* Fill detailed device_state_info now that we know it is used by extd. callback */
3413                         first_extended_cb_call = 0;
3414                         get_device_state_causing_channels(device_state_info);
3415                 }
3416                 if (state_cb->extended || !same_state) {
3417                         execute_state_callback(state_cb->change_cb,
3418                                 context_name,
3419                                 exten_name,
3420                                 state_cb->data,
3421                                 AST_HINT_UPDATE_DEVICE,
3422                                 hint,
3423                                 state_cb->extended ? device_state_info : NULL);
3424                 }
3425         }
3426         ao2_iterator_destroy(&cb_iter);
3427
3428         ao2_cleanup(device_state_info);
3429 }
3430
3431 static void presence_state_notify_callbacks(struct ast_hint *hint, struct ast_str **hint_app,
3432                                             struct ast_presence_state_message *presence_state)
3433 {
3434         struct ao2_iterator cb_iter;
3435         struct ast_state_cb *state_cb;
3436         char context_name[AST_MAX_CONTEXT];
3437         char exten_name[AST_MAX_EXTENSION];
3438
3439         ao2_lock(hint);
3440         if (!hint->exten) {
3441                 /* The extension has already been destroyed */
3442                 ao2_unlock(hint);
3443                 return;
3444         }
3445
3446         /*
3447          * Save off strings in case the hint extension gets destroyed
3448          * while we are notifying the watchers.
3449          */
3450         ast_copy_string(context_name,
3451                         ast_get_context_name(ast_get_extension_context(hint->exten)),
3452                         sizeof(context_name));
3453         ast_copy_string(exten_name, ast_get_extension_name(hint->exten),
3454                         sizeof(exten_name));
3455         ast_str_set(hint_app, 0, "%s", ast_get_extension_app(hint->exten));
3456         ao2_unlock(hint);
3457
3458         /* Check to see if update is necessary */
3459         if ((hint->last_presence_state == presence_state->state) &&
3460             ((hint->last_presence_subtype && presence_state->subtype &&
3461               !strcmp(hint->last_presence_subtype, pre