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