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