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