2 * Asterisk -- An open source telephony toolkit.
4 * Copyright (C) 1999 - 2008, Digium, Inc.
6 * Mark Spencer <markster@digium.com>
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.
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.
21 * \brief Core PBX routines.
23 * \author Mark Spencer <markster@digium.com>
27 ASTERISK_FILE_VERSION(__FILE__, "$Revision$")
29 #include "asterisk/_private.h"
30 #include "asterisk/paths.h" /* use ast_config_AST_SYSTEM_NAME */
34 #if defined(HAVE_SYSINFO)
35 #include <sys/sysinfo.h>
38 #include <sys/loadavg.h>
41 #include "asterisk/lock.h"
42 #include "asterisk/cli.h"
43 #include "asterisk/pbx.h"
44 #include "asterisk/channel.h"
45 #include "asterisk/file.h"
46 #include "asterisk/callerid.h"
47 #include "asterisk/cdr.h"
48 #include "asterisk/cel.h"
49 #include "asterisk/config.h"
50 #include "asterisk/term.h"
51 #include "asterisk/time.h"
52 #include "asterisk/manager.h"
53 #include "asterisk/ast_expr.h"
54 #include "asterisk/linkedlists.h"
55 #define SAY_STUBS /* generate declarations and stubs for say methods */
56 #include "asterisk/say.h"
57 #include "asterisk/utils.h"
58 #include "asterisk/causes.h"
59 #include "asterisk/musiconhold.h"
60 #include "asterisk/app.h"
61 #include "asterisk/devicestate.h"
62 #include "asterisk/event.h"
63 #include "asterisk/hashtab.h"
64 #include "asterisk/module.h"
65 #include "asterisk/indications.h"
66 #include "asterisk/taskprocessor.h"
67 #include "asterisk/xmldoc.h"
68 #include "asterisk/astobj2.h"
71 * \note I M P O R T A N T :
73 * The speed of extension handling will likely be among the most important
74 * aspects of this PBX. The switching scheme as it exists right now isn't
75 * terribly bad (it's O(N+M), where N is the # of extensions and M is the avg #
76 * of priorities, but a constant search time here would be great ;-)
78 * A new algorithm to do searching based on a 'compiled' pattern tree is introduced
79 * here, and shows a fairly flat (constant) search time, even for over
82 * Also, using a hash table for context/priority name lookup can help prevent
83 * the find_extension routines from absorbing exponential cpu cycles as the number
84 * of contexts/priorities grow. I've previously tested find_extension with red-black trees,
85 * which have O(log2(n)) speed. Right now, I'm using hash tables, which do
86 * searches (ideally) in O(1) time. While these techniques do not yield much
87 * speed in small dialplans, they are worth the trouble in large dialplans.
92 <application name="Answer" language="en_US">
94 Answer a channel if ringing.
97 <parameter name="delay">
98 <para>Asterisk will wait this number of milliseconds before returning to
99 the dialplan after answering the call.</para>
101 <parameter name="nocdr">
102 <para>Asterisk will send an answer signal to the calling phone, but will not
103 set the disposition or answer time in the CDR for this call.</para>
107 <para>If the call has not been answered, this application will
108 answer it. Otherwise, it has no effect on the call.</para>
111 <ref type="application">Hangup</ref>
114 <application name="BackGround" language="en_US">
116 Play an audio file while waiting for digits of an extension to go to.
119 <parameter name="filenames" required="true" argsep="&">
120 <argument name="filename1" required="true" />
121 <argument name="filename2" multiple="true" />
123 <parameter name="options">
126 <para>Causes the playback of the message to be skipped
127 if the channel is not in the <literal>up</literal> state (i.e. it
128 hasn't been answered yet). If this happens, the
129 application will return immediately.</para>
132 <para>Don't answer the channel before playing the files.</para>
135 <para>Only break if a digit hit matches a one digit
136 extension in the destination context.</para>
140 <parameter name="langoverride">
141 <para>Explicitly specifies which language to attempt to use for the requested sound files.</para>
143 <parameter name="context">
144 <para>This is the dialplan context that this application will use when exiting
145 to a dialed extension.</para>
149 <para>This application will play the given list of files <emphasis>(do not put extension)</emphasis>
150 while waiting for an extension to be dialed by the calling channel. To continue waiting
151 for digits after this application has finished playing files, the <literal>WaitExten</literal>
152 application should be used.</para>
153 <para>If one of the requested sound files does not exist, call processing will be terminated.</para>
154 <para>This application sets the following channel variable upon completion:</para>
156 <variable name="BACKGROUNDSTATUS">
157 <para>The status of the background attempt as a text string.</para>
158 <value name="SUCCESS" />
159 <value name="FAILED" />
164 <ref type="application">ControlPlayback</ref>
165 <ref type="application">WaitExten</ref>
166 <ref type="application">BackgroundDetect</ref>
167 <ref type="function">TIMEOUT</ref>
170 <application name="Busy" language="en_US">
172 Indicate the Busy condition.
175 <parameter name="timeout">
176 <para>If specified, the calling channel will be hung up after the specified number of seconds.
177 Otherwise, this application will wait until the calling channel hangs up.</para>
181 <para>This application will indicate the busy condition to the calling channel.</para>
184 <ref type="application">Congestion</ref>
185 <ref type="application">Progress</ref>
186 <ref type="application">Playtones</ref>
187 <ref type="application">Hangup</ref>
190 <application name="Congestion" language="en_US">
192 Indicate the Congestion condition.
195 <parameter name="timeout">
196 <para>If specified, the calling channel will be hung up after the specified number of seconds.
197 Otherwise, this application will wait until the calling channel hangs up.</para>
201 <para>This application will indicate the congestion condition to the calling channel.</para>
204 <ref type="application">Busy</ref>
205 <ref type="application">Progress</ref>
206 <ref type="application">Playtones</ref>
207 <ref type="application">Hangup</ref>
210 <application name="ExecIfTime" language="en_US">
212 Conditional application execution based on the current time.
215 <parameter name="day_condition" required="true">
216 <argument name="times" required="true" />
217 <argument name="weekdays" required="true" />
218 <argument name="mdays" required="true" />
219 <argument name="months" required="true" />
220 <argument name="timezone" required="false" />
222 <parameter name="appname" required="true" hasparams="optional">
223 <argument name="appargs" required="true" />
227 <para>This application will execute the specified dialplan application, with optional
228 arguments, if the current time matches the given time specification.</para>
231 <ref type="application">Exec</ref>
232 <ref type="application">TryExec</ref>
235 <application name="Goto" language="en_US">
237 Jump to a particular priority, extension, or context.
240 <parameter name="context" />
241 <parameter name="extensions" />
242 <parameter name="priority" required="true" />
245 <para>This application will set the current context, extension, and priority in the channel structure.
246 After it completes, the pbx engine will continue dialplan execution at the specified location.
247 If no specific <replaceable>extension</replaceable>, or <replaceable>extension</replaceable> and
248 <replaceable>context</replaceable>, are specified, then this application will
249 just set the specified <replaceable>priority</replaceable> of the current extension.</para>
250 <para>At least a <replaceable>priority</replaceable> is required as an argument, or the goto will
251 return a <literal>-1</literal>, and the channel and call will be terminated.</para>
252 <para>If the location that is put into the channel information is bogus, and asterisk cannot
253 find that location in the dialplan, then the execution engine will try to find and execute the code in
254 the <literal>i</literal> (invalid) extension in the current context. If that does not exist, it will try to execute the
255 <literal>h</literal> extension. If neither the <literal>h</literal> nor <literal>i</literal> extensions
256 have been defined, the channel is hung up, and the execution of instructions on the channel is terminated.
257 What this means is that, for example, you specify a context that does not exist, then
258 it will not be possible to find the <literal>h</literal> or <literal>i</literal> extensions,
259 and the call will terminate!</para>
262 <ref type="application">GotoIf</ref>
263 <ref type="application">GotoIfTime</ref>
264 <ref type="application">Gosub</ref>
265 <ref type="application">Macro</ref>
268 <application name="GotoIf" language="en_US">
273 <parameter name="condition" required="true" />
274 <parameter name="destination" required="true" argsep=":">
275 <argument name="labeliftrue">
276 <para>Continue at <replaceable>labeliftrue</replaceable> if the condition is true.</para>
278 <argument name="labeliffalse">
279 <para>Continue at <replaceable>labeliffalse</replaceable> if the condition is false.</para>
284 <para>This application will set the current context, extension, and priority in the channel structure
285 based on the evaluation of the given condition. After this application completes, the
286 pbx engine will continue dialplan execution at the specified location in the dialplan.
287 The labels are specified with the same syntax as used within the Goto application.
288 If the label chosen by the condition is omitted, no jump is performed, and the execution passes to the
289 next instruction. If the target location is bogus, and does not exist, the execution engine will try
290 to find and execute the code in the <literal>i</literal> (invalid) extension in the current context.
291 If that does not exist, it will try to execute the <literal>h</literal> extension.
292 If neither the <literal>h</literal> nor <literal>i</literal> extensions have been defined,
293 the channel is hung up, and the execution of instructions on the channel is terminated.
294 Remember that this command can set the current context, and if the context specified
295 does not exist, then it will not be able to find any 'h' or 'i' extensions there, and
296 the channel and call will both be terminated!.</para>
299 <ref type="application">Goto</ref>
300 <ref type="application">GotoIfTime</ref>
301 <ref type="application">GosubIf</ref>
302 <ref type="application">MacroIf</ref>
305 <application name="GotoIfTime" language="en_US">
307 Conditional Goto based on the current time.
310 <parameter name="condition" required="true">
311 <argument name="times" required="true" />
312 <argument name="weekdays" required="true" />
313 <argument name="mdays" required="true" />
314 <argument name="months" required="true" />
315 <argument name="timezone" required="false" />
317 <parameter name="destination" required="true" argsep=":">
318 <argument name="labeliftrue" />
319 <argument name="labeliffalse" />
323 <para>This application will set the context, extension, and priority in the channel structure
324 based on the evaluation of the given time specification. After this application completes,
325 the pbx engine will continue dialplan execution at the specified location in the dialplan.
326 If the current time is within the given time specification, the channel will continue at
327 <replaceable>labeliftrue</replaceable>. Otherwise the channel will continue at <replaceable>labeliffalse</replaceable>.
328 If the label chosen by the condition is omitted, no jump is performed, and execution passes to the next
329 instruction. If the target jump location is bogus, the same actions would be taken as for <literal>Goto</literal>.
330 Further information on the time specification can be found in examples
331 illustrating how to do time-based context includes in the dialplan.</para>
334 <ref type="application">GotoIf</ref>
335 <ref type="function">IFTIME</ref>
336 <ref type="function">TESTTIME</ref>
339 <application name="ImportVar" language="en_US">
341 Import a variable from a channel into a new variable.
344 <parameter name="newvar" required="true" />
345 <parameter name="vardata" required="true">
346 <argument name="channelname" required="true" />
347 <argument name="variable" required="true" />
351 <para>This application imports a <replaceable>variable</replaceable> from the specified
352 <replaceable>channel</replaceable> (as opposed to the current one) and stores it as a variable
353 (<replaceable>newvar</replaceable>) in the current channel (the channel that is calling this
354 application). Variables created by this application have the same inheritance properties as those
355 created with the <literal>Set</literal> application.</para>
358 <ref type="application">Set</ref>
361 <application name="Hangup" language="en_US">
363 Hang up the calling channel.
366 <parameter name="causecode">
367 <para>If a <replaceable>causecode</replaceable> is given the channel's
368 hangup cause will be set to the given value.</para>
372 <para>This application will hang up the calling channel.</para>
375 <ref type="application">Answer</ref>
376 <ref type="application">Busy</ref>
377 <ref type="application">Congestion</ref>
380 <application name="Incomplete" language="en_US">
382 Returns AST_PBX_INCOMPLETE value.
386 <para>If specified, then Incomplete will not attempt to answer the channel first.</para>
387 <note><para>Most channel types need to be in Answer state in order to receive DTMF.</para></note>
391 <para>Signals the PBX routines that the previous matched extension is incomplete
392 and that further input should be allowed before matching can be considered
393 to be complete. Can be used within a pattern match when certain criteria warrants
394 a longer match.</para>
397 <application name="NoOp" language="en_US">
399 Do Nothing (No Operation).
402 <parameter name="text">
403 <para>Any text provided can be viewed at the Asterisk CLI.</para>
407 <para>This application does nothing. However, it is useful for debugging purposes.</para>
408 <para>This method can be used to see the evaluations of variables or functions without having any effect.</para>
411 <ref type="application">Verbose</ref>
412 <ref type="application">Log</ref>
415 <application name="Proceeding" language="en_US">
421 <para>This application will request that a proceeding message be provided to the calling channel.</para>
424 <application name="Progress" language="en_US">
430 <para>This application will request that in-band progress information be provided to the calling channel.</para>
433 <ref type="application">Busy</ref>
434 <ref type="application">Congestion</ref>
435 <ref type="application">Ringing</ref>
436 <ref type="application">Playtones</ref>
439 <application name="RaiseException" language="en_US">
441 Handle an exceptional condition.
444 <parameter name="reason" required="true" />
447 <para>This application will jump to the <literal>e</literal> extension in the current context, setting the
448 dialplan function EXCEPTION(). If the <literal>e</literal> extension does not exist, the call will hangup.</para>
451 <ref type="function">Exception</ref>
454 <application name="ResetCDR" language="en_US">
456 Resets the Call Data Record.
459 <parameter name="options">
462 <para>Store the current CDR record before resetting it.</para>
465 <para>Store any stacked records.</para>
468 <para>Save CDR variables.</para>
471 <para>Enable CDR only (negate effects of NoCDR).</para>
477 <para>This application causes the Call Data Record to be reset.</para>
480 <ref type="application">ForkCDR</ref>
481 <ref type="application">NoCDR</ref>
484 <application name="Ringing" language="en_US">
486 Indicate ringing tone.
490 <para>This application will request that the channel indicate a ringing tone to the user.</para>
493 <ref type="application">Busy</ref>
494 <ref type="application">Congestion</ref>
495 <ref type="application">Progress</ref>
496 <ref type="application">Playtones</ref>
499 <application name="SayAlpha" language="en_US">
504 <parameter name="string" required="true" />
507 <para>This application will play the sounds that correspond to the letters of the
508 given <replaceable>string</replaceable>.</para>
511 <ref type="application">SayDigits</ref>
512 <ref type="application">SayNumber</ref>
513 <ref type="application">SayPhonetic</ref>
514 <ref type="function">CHANNEL</ref>
517 <application name="SayDigits" language="en_US">
522 <parameter name="digits" required="true" />
525 <para>This application will play the sounds that correspond to the digits of
526 the given number. This will use the language that is currently set for the channel.</para>
529 <ref type="application">SayAlpha</ref>
530 <ref type="application">SayNumber</ref>
531 <ref type="application">SayPhonetic</ref>
532 <ref type="function">CHANNEL</ref>
535 <application name="SayNumber" language="en_US">
540 <parameter name="digits" required="true" />
541 <parameter name="gender" />
544 <para>This application will play the sounds that correspond to the given <replaceable>digits</replaceable>.
545 Optionally, a <replaceable>gender</replaceable> may be specified. This will use the language that is currently
546 set for the channel. See the CHANNEL() function for more information on setting the language for the channel.</para>
549 <ref type="application">SayAlpha</ref>
550 <ref type="application">SayDigits</ref>
551 <ref type="application">SayPhonetic</ref>
552 <ref type="function">CHANNEL</ref>
555 <application name="SayPhonetic" language="en_US">
560 <parameter name="string" required="true" />
563 <para>This application will play the sounds from the phonetic alphabet that correspond to the
564 letters in the given <replaceable>string</replaceable>.</para>
567 <ref type="application">SayAlpha</ref>
568 <ref type="application">SayDigits</ref>
569 <ref type="application">SayNumber</ref>
572 <application name="Set" language="en_US">
574 Set channel variable or function value.
577 <parameter name="name" required="true" />
578 <parameter name="value" required="true" />
581 <para>This function can be used to set the value of channel variables or dialplan functions.
582 When setting variables, if the variable name is prefixed with <literal>_</literal>,
583 the variable will be inherited into channels created from the current channel.
584 If the variable name is prefixed with <literal>__</literal>, the variable will be
585 inherited into channels created from the current channel and all children channels.</para>
586 <note><para>If (and only if), in <filename>/etc/asterisk/asterisk.conf</filename>, you have
587 a <literal>[compat]</literal> category, and you have <literal>app_set = 1.4</literal> under that, then
588 the behavior of this app changes, and strips surrounding quotes from the right hand side as
589 it did previously in 1.4.
590 The advantages of not stripping out quoting, and not caring about the separator characters (comma and vertical bar)
591 were sufficient to make these changes in 1.6. Confusion about how many backslashes would be needed to properly
592 protect separators and quotes in various database access strings has been greatly
593 reduced by these changes.</para></note>
596 <ref type="application">MSet</ref>
597 <ref type="function">GLOBAL</ref>
598 <ref type="function">SET</ref>
599 <ref type="function">ENV</ref>
602 <application name="MSet" language="en_US">
604 Set channel variable(s) or function value(s).
607 <parameter name="set1" required="true" argsep="=">
608 <argument name="name1" required="true" />
609 <argument name="value1" required="true" />
611 <parameter name="set2" multiple="true" argsep="=">
612 <argument name="name2" required="true" />
613 <argument name="value2" required="true" />
617 <para>This function can be used to set the value of channel variables or dialplan functions.
618 When setting variables, if the variable name is prefixed with <literal>_</literal>,
619 the variable will be inherited into channels created from the current channel
620 If the variable name is prefixed with <literal>__</literal>, the variable will be
621 inherited into channels created from the current channel and all children channels.
622 MSet behaves in a similar fashion to the way Set worked in 1.2/1.4 and is thus
623 prone to doing things that you may not expect. For example, it strips surrounding
624 double-quotes from the right-hand side (value). If you need to put a separator
625 character (comma or vert-bar), you will need to escape them by inserting a backslash
626 before them. Avoid its use if possible.</para>
629 <ref type="application">Set</ref>
632 <application name="SetAMAFlags" language="en_US">
637 <parameter name="flag" />
640 <para>This application will set the channel's AMA Flags for billing purposes.</para>
643 <ref type="function">CDR</ref>
646 <application name="Wait" language="en_US">
651 <parameter name="seconds" required="true">
652 <para>Can be passed with fractions of a second. For example, <literal>1.5</literal> will ask the
653 application to wait for 1.5 seconds.</para>
657 <para>This application waits for a specified number of <replaceable>seconds</replaceable>.</para>
660 <application name="WaitExten" language="en_US">
662 Waits for an extension to be entered.
665 <parameter name="seconds">
666 <para>Can be passed with fractions of a second. For example, <literal>1.5</literal> will ask the
667 application to wait for 1.5 seconds.</para>
669 <parameter name="options">
672 <para>Provide music on hold to the caller while waiting for an extension.</para>
674 <para>Specify the class for music on hold. <emphasis>CHANNEL(musicclass) will
675 be used instead if set</emphasis></para>
682 <para>This application waits for the user to enter a new extension for a specified number
683 of <replaceable>seconds</replaceable>.</para>
684 <xi:include xpointer="xpointer(/docs/application[@name='Macro']/description/warning[2])" />
687 <ref type="application">Background</ref>
688 <ref type="function">TIMEOUT</ref>
691 <function name="EXCEPTION" language="en_US">
693 Retrieve the details of the current dialplan exception.
696 <parameter name="field" required="true">
697 <para>The following fields are available for retrieval:</para>
700 <para>INVALID, ERROR, RESPONSETIMEOUT, ABSOLUTETIMEOUT, or custom
701 value set by the RaiseException() application</para>
703 <enum name="context">
704 <para>The context executing when the exception occurred.</para>
707 <para>The extension executing when the exception occurred.</para>
709 <enum name="priority">
710 <para>The numeric priority executing when the exception occurred.</para>
716 <para>Retrieve the details (specified <replaceable>field</replaceable>) of the current dialplan exception.</para>
719 <ref type="application">RaiseException</ref>
722 <function name="TESTTIME" language="en_US">
724 Sets a time to be used with the channel to test logical conditions.
727 <parameter name="date" required="true" argsep=" ">
728 <para>Date in ISO 8601 format</para>
730 <parameter name="time" required="true" argsep=" ">
731 <para>Time in HH:MM:SS format (24-hour time)</para>
733 <parameter name="zone" required="false">
734 <para>Timezone name</para>
738 <para>To test dialplan timing conditions at times other than the current time, use
739 this function to set an alternate date and time. For example, you may wish to evaluate
740 whether a location will correctly identify to callers that the area is closed on Christmas
741 Day, when Christmas would otherwise fall on a day when the office is normally open.</para>
744 <ref type="application">GotoIfTime</ref>
747 <manager name="ShowDialPlan" language="en_US">
749 Show dialplan contexts and extensions
752 <xi:include xpointer="xpointer(/docs/manager[@name='Login']/syntax/parameter[@name='ActionID'])" />
753 <parameter name="Extension">
754 <para>Show a specific extension.</para>
756 <parameter name="Context">
757 <para>Show a specific context.</para>
761 <para>Show dialplan contexts and extensions. Be aware that showing the full dialplan
762 may take a lot of capacity.</para>
768 #define EXT_DATA_SIZE 256
770 #define EXT_DATA_SIZE 8192
773 #define SWITCH_DATA_LENGTH 256
775 #define VAR_BUF_SIZE 4096
778 #define VAR_SOFTTRAN 2
779 #define VAR_HARDTRAN 3
781 #define BACKGROUND_SKIP (1 << 0)
782 #define BACKGROUND_NOANSWER (1 << 1)
783 #define BACKGROUND_MATCHEXTEN (1 << 2)
784 #define BACKGROUND_PLAYBACK (1 << 3)
786 AST_APP_OPTIONS(background_opts, {
787 AST_APP_OPTION('s', BACKGROUND_SKIP),
788 AST_APP_OPTION('n', BACKGROUND_NOANSWER),
789 AST_APP_OPTION('m', BACKGROUND_MATCHEXTEN),
790 AST_APP_OPTION('p', BACKGROUND_PLAYBACK),
793 #define WAITEXTEN_MOH (1 << 0)
794 #define WAITEXTEN_DIALTONE (1 << 1)
796 AST_APP_OPTIONS(waitexten_opts, {
797 AST_APP_OPTION_ARG('m', WAITEXTEN_MOH, 0),
798 AST_APP_OPTION_ARG('d', WAITEXTEN_DIALTONE, 0),
804 static struct ast_taskprocessor *device_state_tps;
806 AST_THREADSTORAGE(switch_data);
807 AST_THREADSTORAGE(extensionstate_buf);
810 \brief ast_exten: An extension
811 The dialplan is saved as a linked list with each context
812 having it's own linked list of extensions - one item per
816 char *exten; /*!< Extension name */
817 int matchcid; /*!< Match caller id ? */
818 const char *cidmatch; /*!< Caller id to match for this extension */
819 int priority; /*!< Priority */
820 const char *label; /*!< Label */
821 struct ast_context *parent; /*!< The context this extension belongs to */
822 const char *app; /*!< Application to execute */
823 struct ast_app *cached_app; /*!< Cached location of application */
824 void *data; /*!< Data to use (arguments) */
825 void (*datad)(void *); /*!< Data destructor */
826 struct ast_exten *peer; /*!< Next higher priority with our extension */
827 struct ast_hashtab *peer_table; /*!< Priorities list in hashtab form -- only on the head of the peer list */
828 struct ast_hashtab *peer_label_table; /*!< labeled priorities in the peers -- only on the head of the peer list */
829 const char *registrar; /*!< Registrar */
830 struct ast_exten *next; /*!< Extension with a greater ID */
834 /*! \brief ast_include: include= support in extensions.conf */
837 const char *rname; /*!< Context to include */
838 const char *registrar; /*!< Registrar */
839 int hastime; /*!< If time construct exists */
840 struct ast_timing timing; /*!< time construct */
841 struct ast_include *next; /*!< Link them together */
845 /*! \brief ast_sw: Switch statement in extensions.conf */
848 const char *registrar; /*!< Registrar */
849 char *data; /*!< Data load */
851 AST_LIST_ENTRY(ast_sw) list;
855 /*! \brief ast_ignorepat: Ignore patterns in dial plan */
856 struct ast_ignorepat {
857 const char *registrar;
858 struct ast_ignorepat *next;
859 const char pattern[0];
862 /*! \brief match_char: forms a syntax tree for quick matching of extension patterns */
865 int is_pattern; /* the pattern started with '_' */
866 int deleted; /* if this is set, then... don't return it */
867 int specificity; /* simply the strlen of x, or 10 for X, 9 for Z, and 8 for N; and '.' and '!' will add 11 ? */
868 struct match_char *alt_char;
869 struct match_char *next_char;
870 struct ast_exten *exten; /* attached to last char of a pattern for exten */
871 char x[1]; /* the pattern itself-- matches a single char */
874 struct scoreboard /* make sure all fields are 0 before calling new_find_extension */
876 int total_specificity;
878 char last_char; /* set to ! or . if they are the end of the pattern */
879 int canmatch; /* if the string to match was just too short */
880 struct match_char *node;
881 struct ast_exten *canmatch_exten;
882 struct ast_exten *exten;
885 /*! \brief ast_context: An extension context */
887 ast_rwlock_t lock; /*!< A lock to prevent multiple threads from clobbering the context */
888 struct ast_exten *root; /*!< The root of the list of extensions */
889 struct ast_hashtab *root_table; /*!< For exact matches on the extensions in the pattern tree, and for traversals of the pattern_tree */
890 struct match_char *pattern_tree; /*!< A tree to speed up extension pattern matching */
891 struct ast_context *next; /*!< Link them together */
892 struct ast_include *includes; /*!< Include other contexts */
893 struct ast_ignorepat *ignorepats; /*!< Patterns for which to continue playing dialtone */
894 char *registrar; /*!< Registrar -- make sure you malloc this, as the registrar may have to survive module unloads */
895 int refcount; /*!< each module that would have created this context should inc/dec this as appropriate */
896 AST_LIST_HEAD_NOLOCK(, ast_sw) alts; /*!< Alternative switches */
897 ast_mutex_t macrolock; /*!< A lock to implement "exclusive" macros - held whilst a call is executing in the macro */
898 char name[0]; /*!< Name of the context */
901 /*! \brief ast_app: A registered application */
903 int (*execute)(struct ast_channel *chan, const char *data);
904 AST_DECLARE_STRING_FIELDS(
905 AST_STRING_FIELD(synopsis); /*!< Synopsis text for 'show applications' */
906 AST_STRING_FIELD(description); /*!< Description (help text) for 'show application <name>' */
907 AST_STRING_FIELD(syntax); /*!< Syntax text for 'core show applications' */
908 AST_STRING_FIELD(arguments); /*!< Arguments description */
909 AST_STRING_FIELD(seealso); /*!< See also */
912 enum ast_doc_src docsrc; /*!< Where the documentation come from. */
914 AST_RWLIST_ENTRY(ast_app) list; /*!< Next app in list */
915 struct ast_module *module; /*!< Module this app belongs to */
916 char name[0]; /*!< Name of the application */
919 /*! \brief ast_state_cb: An extension state notify register item */
920 struct ast_state_cb {
921 /*! Watcher ID returned when registered. */
923 /*! Arbitrary data passed for callbacks. */
925 /*! Callback when state changes. */
926 ast_state_cb_type change_cb;
927 /*! Callback when destroyed so any resources given by the registerer can be freed. */
928 ast_state_cb_destroy_type destroy_cb;
929 /*! \note Only used by ast_merge_contexts_and_delete */
930 AST_LIST_ENTRY(ast_state_cb) entry;
934 * \brief Structure for dial plan hints
936 * \note Hints are pointers from an extension in the dialplan to
937 * one or more devices (tech/name)
939 * See \ref AstExtState
943 * \brief Hint extension
946 * Will never be NULL while the hint is in the hints container.
948 struct ast_exten *exten;
949 struct ao2_container *callbacks; /*!< Callback container for this extension */
950 int laststate; /*!< Last known state */
951 char context_name[AST_MAX_CONTEXT];/*!< Context of destroyed hint extension. */
952 char exten_name[AST_MAX_EXTENSION];/*!< Extension of destroyed hint extension. */
956 #define HINTDEVICE_DATA_LENGTH 16
957 AST_THREADSTORAGE(hintdevice_data);
959 /* --- Hash tables of various objects --------*/
961 #define HASH_EXTENHINT_SIZE 17
963 #define HASH_EXTENHINT_SIZE 563
967 /*! \brief Container for hint devices */
968 static struct ao2_container *hintdevices;
971 * \brief Structure for dial plan hint devices
972 * \note hintdevice is one device pointing to a hint.
974 struct ast_hintdevice {
976 * \brief Hint this hintdevice belongs to.
977 * \note Holds a reference to the hint object.
979 struct ast_hint *hint;
980 /*! Name of the hint device. */
986 * \note Using the device for hash
988 static int hintdevice_hash_cb(const void *obj, const int flags)
990 const struct ast_hintdevice *ext = obj;
992 return ast_str_case_hash(ext->hintdevice);
995 * \note Devices on hints are not unique so no CMP_STOP is returned
996 * Dont use ao2_find against hintdevices container cause there always
997 * could be more than one result.
999 static int hintdevice_cmp_multiple(void *obj, void *arg, int flags)
1001 struct ast_hintdevice *ext = obj, *ext2 = arg;
1003 return !strcasecmp(ext->hintdevice, ext2->hintdevice) ? CMP_MATCH : 0;
1007 * \details This is used with ao2_callback to remove old devices
1008 * when they are linked to the hint
1010 static int hintdevice_remove_cb(void *deviceobj, void *arg, int flags)
1012 struct ast_hintdevice *device = deviceobj;
1013 struct ast_hint *hint = arg;
1015 return (device->hint == hint) ? CMP_MATCH : 0;
1018 static int remove_hintdevice(struct ast_hint *hint)
1020 /* iterate through all devices and remove the devices which are linked to this hint */
1021 ao2_t_callback(hintdevices, OBJ_NODATA | OBJ_MULTIPLE | OBJ_UNLINK,
1022 hintdevice_remove_cb, hint,
1023 "callback to remove all devices which are linked to a hint");
1029 * \brief Destroy the given hintdevice object.
1031 * \param obj Hint device to destroy.
1035 static void hintdevice_destroy(void *obj)
1037 struct ast_hintdevice *doomed = obj;
1040 ao2_ref(doomed->hint, -1);
1041 doomed->hint = NULL;
1045 /*! \brief add hintdevice structure and link it into the container.
1047 static int add_hintdevice(struct ast_hint *hint, const char *devicelist)
1049 struct ast_str *str;
1052 struct ast_hintdevice *device;
1055 if (!hint || !devicelist) {
1056 /* Trying to add garbage? Don't bother. */
1059 if (!(str = ast_str_thread_get(&hintdevice_data, 16))) {
1062 ast_str_set(&str, 0, "%s", devicelist);
1063 parse = ast_str_buffer(str);
1065 while ((cur = strsep(&parse, "&"))) {
1066 devicelength = strlen(cur);
1067 device = ao2_t_alloc(sizeof(*device) + devicelength, hintdevice_destroy,
1068 "allocating a hintdevice structure");
1072 strcpy(device->hintdevice, cur);
1074 device->hint = hint;
1075 ao2_t_link(hintdevices, device, "Linking device into hintdevice container.");
1076 ao2_t_ref(device, -1, "hintdevice is linked so we can unref");
1083 static const struct cfextension_states {
1084 int extension_state;
1085 const char * const text;
1086 } extension_states[] = {
1087 { AST_EXTENSION_NOT_INUSE, "Idle" },
1088 { AST_EXTENSION_INUSE, "InUse" },
1089 { AST_EXTENSION_BUSY, "Busy" },
1090 { AST_EXTENSION_UNAVAILABLE, "Unavailable" },
1091 { AST_EXTENSION_RINGING, "Ringing" },
1092 { AST_EXTENSION_INUSE | AST_EXTENSION_RINGING, "InUse&Ringing" },
1093 { AST_EXTENSION_ONHOLD, "Hold" },
1094 { AST_EXTENSION_INUSE | AST_EXTENSION_ONHOLD, "InUse&Hold" }
1097 struct statechange {
1098 AST_LIST_ENTRY(statechange) entry;
1102 struct pbx_exception {
1103 AST_DECLARE_STRING_FIELDS(
1104 AST_STRING_FIELD(context); /*!< Context associated with this exception */
1105 AST_STRING_FIELD(exten); /*!< Exten associated with this exception */
1106 AST_STRING_FIELD(reason); /*!< The exception reason */
1109 int priority; /*!< Priority associated with this exception */
1112 static int pbx_builtin_answer(struct ast_channel *, const char *);
1113 static int pbx_builtin_goto(struct ast_channel *, const char *);
1114 static int pbx_builtin_hangup(struct ast_channel *, const char *);
1115 static int pbx_builtin_background(struct ast_channel *, const char *);
1116 static int pbx_builtin_wait(struct ast_channel *, const char *);
1117 static int pbx_builtin_waitexten(struct ast_channel *, const char *);
1118 static int pbx_builtin_incomplete(struct ast_channel *, const char *);
1119 static int pbx_builtin_resetcdr(struct ast_channel *, const char *);
1120 static int pbx_builtin_setamaflags(struct ast_channel *, const char *);
1121 static int pbx_builtin_ringing(struct ast_channel *, const char *);
1122 static int pbx_builtin_proceeding(struct ast_channel *, const char *);
1123 static int pbx_builtin_progress(struct ast_channel *, const char *);
1124 static int pbx_builtin_congestion(struct ast_channel *, const char *);
1125 static int pbx_builtin_busy(struct ast_channel *, const char *);
1126 static int pbx_builtin_noop(struct ast_channel *, const char *);
1127 static int pbx_builtin_gotoif(struct ast_channel *, const char *);
1128 static int pbx_builtin_gotoiftime(struct ast_channel *, const char *);
1129 static int pbx_builtin_execiftime(struct ast_channel *, const char *);
1130 static int pbx_builtin_saynumber(struct ast_channel *, const char *);
1131 static int pbx_builtin_saydigits(struct ast_channel *, const char *);
1132 static int pbx_builtin_saycharacters(struct ast_channel *, const char *);
1133 static int pbx_builtin_sayphonetic(struct ast_channel *, const char *);
1134 static int matchcid(const char *cidpattern, const char *callerid);
1136 static void log_match_char_tree(struct match_char *node, char *prefix); /* for use anywhere */
1138 static int pbx_builtin_importvar(struct ast_channel *, const char *);
1139 static void set_ext_pri(struct ast_channel *c, const char *exten, int pri);
1140 static void new_find_extension(const char *str, struct scoreboard *score,
1141 struct match_char *tree, int length, int spec, const char *callerid,
1142 const char *label, enum ext_match_t action);
1143 static struct match_char *already_in_tree(struct match_char *current, char *pat, int is_pattern);
1144 static struct match_char *add_exten_to_pattern_tree(struct ast_context *con,
1145 struct ast_exten *e1, int findonly);
1146 static void create_match_char_tree(struct ast_context *con);
1147 static struct ast_exten *get_canmatch_exten(struct match_char *node);
1148 static void destroy_pattern_tree(struct match_char *pattern_tree);
1149 static int hashtab_compare_extens(const void *ha_a, const void *ah_b);
1150 static int hashtab_compare_exten_numbers(const void *ah_a, const void *ah_b);
1151 static int hashtab_compare_exten_labels(const void *ah_a, const void *ah_b);
1152 static unsigned int hashtab_hash_extens(const void *obj);
1153 static unsigned int hashtab_hash_priority(const void *obj);
1154 static unsigned int hashtab_hash_labels(const void *obj);
1155 static void __ast_internal_context_destroy( struct ast_context *con);
1156 static int ast_add_extension_nolock(const char *context, int replace, const char *extension,
1157 int priority, const char *label, const char *callerid,
1158 const char *application, void *data, void (*datad)(void *), const char *registrar);
1159 static int ast_add_extension2_lockopt(struct ast_context *con,
1160 int replace, const char *extension, int priority, const char *label, const char *callerid,
1161 const char *application, void *data, void (*datad)(void *),
1162 const char *registrar, int lock_context);
1163 static struct ast_context *find_context_locked(const char *context);
1164 static struct ast_context *find_context(const char *context);
1168 * \brief Character array comparison function for qsort.
1170 * \param a Left side object.
1171 * \param b Right side object.
1173 * \retval <0 if a < b
1174 * \retval =0 if a = b
1175 * \retval >0 if a > b
1177 static int compare_char(const void *a, const void *b)
1179 const unsigned char *ac = a;
1180 const unsigned char *bc = b;
1185 /* labels, contexts are case sensitive priority numbers are ints */
1186 int ast_hashtab_compare_contexts(const void *ah_a, const void *ah_b)
1188 const struct ast_context *ac = ah_a;
1189 const struct ast_context *bc = ah_b;
1190 if (!ac || !bc) /* safety valve, but it might prevent a crash you'd rather have happen */
1192 /* assume context names are registered in a string table! */
1193 return strcmp(ac->name, bc->name);
1196 static int hashtab_compare_extens(const void *ah_a, const void *ah_b)
1198 const struct ast_exten *ac = ah_a;
1199 const struct ast_exten *bc = ah_b;
1200 int x = strcmp(ac->exten, bc->exten);
1201 if (x) { /* if exten names are diff, then return */
1205 /* but if they are the same, do the cidmatch values match? */
1206 if (ac->matchcid && bc->matchcid) {
1207 return strcmp(ac->cidmatch,bc->cidmatch);
1208 } else if (!ac->matchcid && !bc->matchcid) {
1209 return 0; /* if there's no matchcid on either side, then this is a match */
1211 return 1; /* if there's matchcid on one but not the other, they are different */
1215 static int hashtab_compare_exten_numbers(const void *ah_a, const void *ah_b)
1217 const struct ast_exten *ac = ah_a;
1218 const struct ast_exten *bc = ah_b;
1219 return ac->priority != bc->priority;
1222 static int hashtab_compare_exten_labels(const void *ah_a, const void *ah_b)
1224 const struct ast_exten *ac = ah_a;
1225 const struct ast_exten *bc = ah_b;
1226 return strcmp(S_OR(ac->label, ""), S_OR(bc->label, ""));
1229 unsigned int ast_hashtab_hash_contexts(const void *obj)
1231 const struct ast_context *ac = obj;
1232 return ast_hashtab_hash_string(ac->name);
1235 static unsigned int hashtab_hash_extens(const void *obj)
1237 const struct ast_exten *ac = obj;
1238 unsigned int x = ast_hashtab_hash_string(ac->exten);
1241 y = ast_hashtab_hash_string(ac->cidmatch);
1245 static unsigned int hashtab_hash_priority(const void *obj)
1247 const struct ast_exten *ac = obj;
1248 return ast_hashtab_hash_int(ac->priority);
1251 static unsigned int hashtab_hash_labels(const void *obj)
1253 const struct ast_exten *ac = obj;
1254 return ast_hashtab_hash_string(S_OR(ac->label, ""));
1258 AST_RWLOCK_DEFINE_STATIC(globalslock);
1259 static struct varshead globals = AST_LIST_HEAD_NOLOCK_INIT_VALUE;
1261 static int autofallthrough = 1;
1262 static int extenpatternmatchnew = 0;
1263 static char *overrideswitch = NULL;
1265 /*! \brief Subscription for device state change events */
1266 static struct ast_event_sub *device_state_sub;
1268 AST_MUTEX_DEFINE_STATIC(maxcalllock);
1269 static int countcalls;
1270 static int totalcalls;
1272 static AST_RWLIST_HEAD_STATIC(acf_root, ast_custom_function);
1274 /*! \brief Declaration of builtin applications */
1275 static struct pbx_builtin {
1276 char name[AST_MAX_APP];
1277 int (*execute)(struct ast_channel *chan, const char *data);
1280 /* These applications are built into the PBX core and do not
1281 need separate modules */
1283 { "Answer", pbx_builtin_answer },
1284 { "BackGround", pbx_builtin_background },
1285 { "Busy", pbx_builtin_busy },
1286 { "Congestion", pbx_builtin_congestion },
1287 { "ExecIfTime", pbx_builtin_execiftime },
1288 { "Goto", pbx_builtin_goto },
1289 { "GotoIf", pbx_builtin_gotoif },
1290 { "GotoIfTime", pbx_builtin_gotoiftime },
1291 { "ImportVar", pbx_builtin_importvar },
1292 { "Hangup", pbx_builtin_hangup },
1293 { "Incomplete", pbx_builtin_incomplete },
1294 { "NoOp", pbx_builtin_noop },
1295 { "Proceeding", pbx_builtin_proceeding },
1296 { "Progress", pbx_builtin_progress },
1297 { "RaiseException", pbx_builtin_raise_exception },
1298 { "ResetCDR", pbx_builtin_resetcdr },
1299 { "Ringing", pbx_builtin_ringing },
1300 { "SayAlpha", pbx_builtin_saycharacters },
1301 { "SayDigits", pbx_builtin_saydigits },
1302 { "SayNumber", pbx_builtin_saynumber },
1303 { "SayPhonetic", pbx_builtin_sayphonetic },
1304 { "Set", pbx_builtin_setvar },
1305 { "MSet", pbx_builtin_setvar_multiple },
1306 { "SetAMAFlags", pbx_builtin_setamaflags },
1307 { "Wait", pbx_builtin_wait },
1308 { "WaitExten", pbx_builtin_waitexten }
1311 static struct ast_context *contexts;
1312 static struct ast_hashtab *contexts_table = NULL;
1315 * \brief Lock for the ast_context list
1317 * This lock MUST be recursive, or a deadlock on reload may result. See
1318 * https://issues.asterisk.org/view.php?id=17643
1320 AST_MUTEX_DEFINE_STATIC(conlock);
1323 * \brief Lock to hold off restructuring of hints by ast_merge_contexts_and_delete.
1325 AST_MUTEX_DEFINE_STATIC(context_merge_lock);
1327 static AST_RWLIST_HEAD_STATIC(apps, ast_app);
1329 static AST_RWLIST_HEAD_STATIC(switches, ast_switch);
1331 static int stateid = 1;
1333 * \note When holding this container's lock, do _not_ do
1334 * anything that will cause conlock to be taken, unless you
1335 * _already_ hold it. The ast_merge_contexts_and_delete function
1336 * will take the locks in conlock/hints order, so any other
1337 * paths that require both locks must also take them in that
1340 static struct ao2_container *hints;
1342 static struct ao2_container *statecbs;
1344 #ifdef CONTEXT_DEBUG
1346 /* these routines are provided for doing run-time checks
1347 on the extension structures, in case you are having
1348 problems, this routine might help you localize where
1349 the problem is occurring. It's kinda like a debug memory
1350 allocator's arena checker... It'll eat up your cpu cycles!
1351 but you'll see, if you call it in the right places,
1352 right where your problems began...
1355 /* you can break on the check_contexts_trouble()
1356 routine in your debugger to stop at the moment
1357 there's a problem */
1358 void check_contexts_trouble(void);
1360 void check_contexts_trouble(void)
1366 int check_contexts(char *, int);
1368 int check_contexts(char *file, int line )
1370 struct ast_hashtab_iter *t1;
1371 struct ast_context *c1, *c2;
1373 struct ast_exten *e1, *e2, *e3;
1374 struct ast_exten ex;
1376 /* try to find inconsistencies */
1377 /* is every context in the context table in the context list and vice-versa ? */
1379 if (!contexts_table) {
1380 ast_log(LOG_NOTICE,"Called from: %s:%d: No contexts_table!\n", file, line);
1384 t1 = ast_hashtab_start_traversal(contexts_table);
1385 while( (c1 = ast_hashtab_next(t1))) {
1386 for(c2=contexts;c2;c2=c2->next) {
1387 if (!strcmp(c1->name, c2->name)) {
1393 ast_log(LOG_NOTICE,"Called from: %s:%d: Could not find the %s context in the linked list\n", file, line, c1->name);
1394 check_contexts_trouble();
1397 ast_hashtab_end_traversal(t1);
1398 for(c2=contexts;c2;c2=c2->next) {
1399 c1 = find_context_locked(c2->name);
1401 ast_log(LOG_NOTICE,"Called from: %s:%d: Could not find the %s context in the hashtab\n", file, line, c2->name);
1402 check_contexts_trouble();
1404 ast_unlock_contexts();
1407 /* loop thru all contexts, and verify the exten structure compares to the
1408 hashtab structure */
1409 for(c2=contexts;c2;c2=c2->next) {
1410 c1 = find_context_locked(c2->name);
1412 ast_unlock_contexts();
1414 /* is every entry in the root list also in the root_table? */
1415 for(e1 = c1->root; e1; e1=e1->next)
1417 char dummy_name[1024];
1418 ex.exten = dummy_name;
1419 ex.matchcid = e1->matchcid;
1420 ex.cidmatch = e1->cidmatch;
1421 ast_copy_string(dummy_name, e1->exten, sizeof(dummy_name));
1422 e2 = ast_hashtab_lookup(c1->root_table, &ex);
1425 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 );
1427 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 );
1429 check_contexts_trouble();
1433 /* is every entry in the root_table also in the root list? */
1434 if (!c2->root_table) {
1436 ast_log(LOG_NOTICE,"Called from: %s:%d: No c2->root_table for context %s!\n", file, line, c2->name);
1440 t1 = ast_hashtab_start_traversal(c2->root_table);
1441 while( (e2 = ast_hashtab_next(t1)) ) {
1442 for(e1=c2->root;e1;e1=e1->next) {
1443 if (!strcmp(e1->exten, e2->exten)) {
1449 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);
1450 check_contexts_trouble();
1454 ast_hashtab_end_traversal(t1);
1457 /* is every priority reflected in the peer_table at the head of the list? */
1459 /* is every entry in the root list also in the root_table? */
1460 /* are the per-extension peer_tables in the right place? */
1462 for(e1 = c2->root; e1; e1 = e1->next) {
1464 for(e2=e1;e2;e2=e2->peer) {
1465 ex.priority = e2->priority;
1466 if (e2 != e1 && e2->peer_table) {
1467 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 );
1468 check_contexts_trouble();
1471 if (e2 != e1 && e2->peer_label_table) {
1472 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 );
1473 check_contexts_trouble();
1476 if (e2 == e1 && !e2->peer_table){
1477 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 );
1478 check_contexts_trouble();
1481 if (e2 == e1 && !e2->peer_label_table) {
1482 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 );
1483 check_contexts_trouble();
1487 e3 = ast_hashtab_lookup(e1->peer_table, &ex);
1489 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 );
1490 check_contexts_trouble();
1494 if (!e1->peer_table){
1495 ast_log(LOG_NOTICE,"Called from: %s:%d: No e1->peer_table!\n", file, line);
1499 /* is every entry in the peer_table also in the peer list? */
1500 t1 = ast_hashtab_start_traversal(e1->peer_table);
1501 while( (e2 = ast_hashtab_next(t1)) ) {
1502 for(e3=e1;e3;e3=e3->peer) {
1503 if (e3->priority == e2->priority) {
1509 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 );
1510 check_contexts_trouble();
1513 ast_hashtab_end_traversal(t1);
1521 \note This function is special. It saves the stack so that no matter
1522 how many times it is called, it returns to the same place */
1523 int pbx_exec(struct ast_channel *c, /*!< Channel */
1524 struct ast_app *app, /*!< Application */
1525 const char *data) /*!< Data for execution */
1528 struct ast_module_user *u = NULL;
1529 const char *saved_c_appl;
1530 const char *saved_c_data;
1532 if (ast_channel_cdr(c) && !ast_check_hangup(c))
1533 ast_cdr_setapp(ast_channel_cdr(c), app->name, data);
1535 /* save channel values */
1536 saved_c_appl= ast_channel_appl(c);
1537 saved_c_data= ast_channel_data(c);
1539 ast_channel_appl_set(c, app->name);
1540 ast_channel_data_set(c, data);
1541 ast_cel_report_event(c, AST_CEL_APP_START, NULL, NULL, NULL);
1544 u = __ast_module_user_add(app->module, c);
1545 if (strcasecmp(app->name, "system") && !ast_strlen_zero(data) &&
1546 strchr(data, '|') && !strchr(data, ',') && !ast_opt_dont_warn) {
1547 ast_log(LOG_WARNING, "The application delimiter is now the comma, not "
1548 "the pipe. Did you forget to convert your dialplan? (%s(%s))\n",
1549 app->name, (char *) data);
1551 res = app->execute(c, S_OR(data, ""));
1552 if (app->module && u)
1553 __ast_module_user_remove(app->module, u);
1554 ast_cel_report_event(c, AST_CEL_APP_END, NULL, NULL, NULL);
1555 /* restore channel values */
1556 ast_channel_appl_set(c, saved_c_appl);
1557 ast_channel_data_set(c, saved_c_data);
1562 /*! Go no deeper than this through includes (not counting loops) */
1563 #define AST_PBX_MAX_STACK 128
1565 /*! \brief Find application handle in linked list
1567 struct ast_app *pbx_findapp(const char *app)
1569 struct ast_app *tmp;
1571 AST_RWLIST_RDLOCK(&apps);
1572 AST_RWLIST_TRAVERSE(&apps, tmp, list) {
1573 if (!strcasecmp(tmp->name, app))
1576 AST_RWLIST_UNLOCK(&apps);
1581 static struct ast_switch *pbx_findswitch(const char *sw)
1583 struct ast_switch *asw;
1585 AST_RWLIST_RDLOCK(&switches);
1586 AST_RWLIST_TRAVERSE(&switches, asw, list) {
1587 if (!strcasecmp(asw->name, sw))
1590 AST_RWLIST_UNLOCK(&switches);
1595 static inline int include_valid(struct ast_include *i)
1600 return ast_check_timing(&(i->timing));
1603 static void pbx_destroy(struct ast_pbx *p)
1608 /* form a tree that fully describes all the patterns in a context's extensions
1609 * in this tree, a "node" represents an individual character or character set
1610 * meant to match the corresponding character in a dial string. The tree
1611 * consists of a series of match_char structs linked in a chain
1612 * via the alt_char pointers. More than one pattern can share the same parts of the
1613 * tree as other extensions with the same pattern to that point.
1614 * My first attempt to duplicate the finding of the 'best' pattern was flawed in that
1615 * I misunderstood the general algorithm. I thought that the 'best' pattern
1616 * was the one with lowest total score. This was not true. Thus, if you have
1617 * patterns "1XXXXX" and "X11111", you would be tempted to say that "X11111" is
1618 * the "best" match because it has fewer X's, and is therefore more specific,
1619 * but this is not how the old algorithm works. It sorts matching patterns
1620 * in a similar collating sequence as sorting alphabetic strings, from left to
1621 * right. Thus, "1XXXXX" comes before "X11111", and would be the "better" match,
1622 * because "1" is more specific than "X".
1623 * So, to accomodate this philosophy, I sort the tree branches along the alt_char
1624 * line so they are lowest to highest in specificity numbers. This way, as soon
1625 * as we encounter our first complete match, we automatically have the "best"
1626 * match and can stop the traversal immediately. Same for CANMATCH/MATCHMORE.
1627 * If anyone would like to resurrect the "wrong" pattern trie searching algorithm,
1628 * they are welcome to revert pbx to before 1 Apr 2008.
1629 * As an example, consider these 4 extensions:
1635 * In the above, between (a) and (d), (a) is a more specific pattern than (d), and would win over
1636 * most numbers. For all numbers beginning with 307754, (b) should always win.
1638 * These pattern should form a (sorted) tree that looks like this:
1639 * { "3" } --next--> { "0" } --next--> { "7" } --next--> { "7" } --next--> { "5" } ... blah ... --> { "X" exten_match: (b) }
1643 * { "f" } --next--> { "a" } --next--> { "x" exten_match: (c) }
1644 * { "N" } --next--> { "X" } --next--> { "X" } --next--> { "N" } --next--> { "X" } ... blah ... --> { "X" exten_match: (a) }
1648 * | { "X" } --next--> { "X" } ... blah ... --> { "X" exten_match: (d) }
1652 * In the above, I could easily turn "N" into "23456789", but I think that a quick "if( *z >= '2' && *z <= '9' )" might take
1653 * fewer CPU cycles than a call to strchr("23456789",*z), where *z is the char to match...
1655 * traversal is pretty simple: one routine merely traverses the alt list, and for each matching char in the pattern, it calls itself
1656 * on the corresponding next pointer, incrementing also the pointer of the string to be matched, and passing the total specificity and length.
1657 * We pass a pointer to a scoreboard down through, also.
1658 * The scoreboard isn't as necessary to the revised algorithm, but I kept it as a handy way to return the matched extension.
1659 * The first complete match ends the traversal, which should make this version of the pattern matcher faster
1660 * the previous. The same goes for "CANMATCH" or "MATCHMORE"; the first such match ends the traversal. In both
1661 * these cases, the reason we can stop immediately, is because the first pattern match found will be the "best"
1662 * according to the sort criteria.
1663 * Hope the limit on stack depth won't be a problem... this routine should
1664 * be pretty lean as far a stack usage goes. Any non-match terminates the recursion down a branch.
1666 * In the above example, with the number "3077549999" as the pattern, the traversor could match extensions a, b and d. All are
1667 * of length 10; they have total specificities of 24580, 10246, and 25090, respectively, not that this matters
1668 * at all. (b) wins purely because the first character "3" is much more specific (lower specificity) than "N". I have
1669 * left the specificity totals in the code as an artifact; at some point, I will strip it out.
1671 * Just how much time this algorithm might save over a plain linear traversal over all possible patterns is unknown,
1672 * because it's a function of how many extensions are stored in a context. With thousands of extensions, the speedup
1673 * can be very noticeable. The new matching algorithm can run several hundreds of times faster, if not a thousand or
1674 * more times faster in extreme cases.
1676 * MatchCID patterns are also supported, and stored in the tree just as the extension pattern is. Thus, you
1677 * can have patterns in your CID field as well.
1682 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)
1684 /* if this extension is marked as deleted, then skip this -- if it never shows
1685 on the scoreboard, it will never be found, nor will halt the traversal. */
1688 board->total_specificity = spec;
1689 board->total_length = length;
1690 board->exten = exten;
1691 board->last_char = last;
1693 #ifdef NEED_DEBUG_HERE
1694 ast_log(LOG_NOTICE,"Scoreboarding (LONGER) %s, len=%d, score=%d\n", exten->exten, length, spec);
1699 static void log_match_char_tree(struct match_char *node, char *prefix)
1702 struct ast_str *my_prefix = ast_str_alloca(1024);
1706 if (node && node->exten)
1707 snprintf(extenstr, sizeof(extenstr), "(%p)", node->exten);
1709 if (strlen(node->x) > 1) {
1710 ast_debug(1, "%s[%s]:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y':'N',
1711 node->deleted? 'D':'-', node->specificity, node->exten? "EXTEN:":"",
1712 node->exten ? node->exten->exten : "", extenstr);
1714 ast_debug(1, "%s%s:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y':'N',
1715 node->deleted? 'D':'-', node->specificity, node->exten? "EXTEN:":"",
1716 node->exten ? node->exten->exten : "", extenstr);
1719 ast_str_set(&my_prefix, 0, "%s+ ", prefix);
1721 if (node->next_char)
1722 log_match_char_tree(node->next_char, ast_str_buffer(my_prefix));
1725 log_match_char_tree(node->alt_char, prefix);
1729 static void cli_match_char_tree(struct match_char *node, char *prefix, int fd)
1732 struct ast_str *my_prefix = ast_str_alloca(1024);
1736 if (node && node->exten)
1737 snprintf(extenstr, sizeof(extenstr), "(%p)", node->exten);
1739 if (strlen(node->x) > 1) {
1740 ast_cli(fd, "%s[%s]:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y' : 'N',
1741 node->deleted ? 'D' : '-', node->specificity, node->exten? "EXTEN:" : "",
1742 node->exten ? node->exten->exten : "", extenstr);
1744 ast_cli(fd, "%s%s:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y' : 'N',
1745 node->deleted ? 'D' : '-', node->specificity, node->exten? "EXTEN:" : "",
1746 node->exten ? node->exten->exten : "", extenstr);
1749 ast_str_set(&my_prefix, 0, "%s+ ", prefix);
1751 if (node->next_char)
1752 cli_match_char_tree(node->next_char, ast_str_buffer(my_prefix), fd);
1755 cli_match_char_tree(node->alt_char, prefix, fd);
1758 static struct ast_exten *get_canmatch_exten(struct match_char *node)
1760 /* find the exten at the end of the rope */
1761 struct match_char *node2 = node;
1763 for (node2 = node; node2; node2 = node2->next_char) {
1765 #ifdef NEED_DEBUG_HERE
1766 ast_log(LOG_NOTICE,"CanMatch_exten returns exten %s(%p)\n", node2->exten->exten, node2->exten);
1768 return node2->exten;
1771 #ifdef NEED_DEBUG_HERE
1772 ast_log(LOG_NOTICE,"CanMatch_exten returns NULL, match_char=%s\n", node->x);
1777 static struct ast_exten *trie_find_next_match(struct match_char *node)
1779 struct match_char *m3;
1780 struct match_char *m4;
1781 struct ast_exten *e3;
1783 if (node && node->x[0] == '.' && !node->x[1]) { /* dot and ! will ALWAYS be next match in a matchmore */
1787 if (node && node->x[0] == '!' && !node->x[1]) {
1791 if (!node || !node->next_char) {
1795 m3 = node->next_char;
1800 for (m4 = m3->alt_char; m4; m4 = m4->alt_char) {
1805 for (m4 = m3; m4; m4 = m4->alt_char) {
1806 e3 = trie_find_next_match(m3);
1816 static char *action2str(enum ext_match_t action)
1836 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)
1838 struct match_char *p; /* note minimal stack storage requirements */
1839 struct ast_exten pattern = { .label = label };
1842 ast_log(LOG_NOTICE,"new_find_extension called with %s on (sub)tree %s action=%s\n", str, tree->x, action2str(action));
1844 ast_log(LOG_NOTICE,"new_find_extension called with %s on (sub)tree NULL action=%s\n", str, action2str(action));
1846 for (p = tree; p; p = p->alt_char) {
1847 if (p->is_pattern) {
1848 if (p->x[0] == 'N') {
1849 if (p->x[1] == 0 && *str >= '2' && *str <= '9' ) {
1850 #define NEW_MATCHER_CHK_MATCH \
1851 if (p->exten && !(*(str + 1))) { /* if a shorter pattern matches along the way, might as well report it */ \
1852 if (action == E_MATCH || action == E_SPAWN || action == E_FINDLABEL) { /* if in CANMATCH/MATCHMORE, don't let matches get in the way */ \
1853 update_scoreboard(score, length + 1, spec + p->specificity, p->exten, 0, callerid, p->deleted, p); \
1854 if (!p->deleted) { \
1855 if (action == E_FINDLABEL) { \
1856 if (ast_hashtab_lookup(score->exten->peer_label_table, &pattern)) { \
1857 ast_debug(4, "Found label in preferred extension\n"); \
1861 ast_debug(4, "returning an exact match-- first found-- %s\n", p->exten->exten); \
1862 return; /* the first match, by definition, will be the best, because of the sorted tree */ \
1868 #define NEW_MATCHER_RECURSE \
1869 if (p->next_char && (*(str + 1) || (p->next_char->x[0] == '/' && p->next_char->x[1] == 0) \
1870 || p->next_char->x[0] == '!')) { \
1871 if (*(str + 1) || p->next_char->x[0] == '!') { \
1872 new_find_extension(str + 1, score, p->next_char, length + 1, spec + p->specificity, callerid, label, action); \
1873 if (score->exten) { \
1874 ast_debug(4 ,"returning an exact match-- %s\n", score->exten->exten); \
1875 return; /* the first match is all we need */ \
1878 new_find_extension("/", score, p->next_char, length + 1, spec + p->specificity, callerid, label, action); \
1879 if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) { \
1880 ast_debug(4,"returning a (can/more) match--- %s\n", score->exten ? score->exten->exten : \
1882 return; /* the first match is all we need */ \
1885 } else if ((p->next_char || action == E_CANMATCH) && !*(str + 1)) { \
1886 score->canmatch = 1; \
1887 score->canmatch_exten = get_canmatch_exten(p); \
1888 if (action == E_CANMATCH || action == E_MATCHMORE) { \
1889 ast_debug(4, "returning a canmatch/matchmore--- str=%s\n", str); \
1894 NEW_MATCHER_CHK_MATCH;
1895 NEW_MATCHER_RECURSE;
1897 } else if (p->x[0] == 'Z') {
1898 if (p->x[1] == 0 && *str >= '1' && *str <= '9' ) {
1899 NEW_MATCHER_CHK_MATCH;
1900 NEW_MATCHER_RECURSE;
1902 } else if (p->x[0] == 'X') {
1903 if (p->x[1] == 0 && *str >= '0' && *str <= '9' ) {
1904 NEW_MATCHER_CHK_MATCH;
1905 NEW_MATCHER_RECURSE;
1907 } else if (p->x[0] == '.' && p->x[1] == 0) {
1908 /* how many chars will the . match against? */
1910 const char *str2 = str;
1911 while (*str2 && *str2 != '/') {
1915 if (p->exten && *str2 != '/') {
1916 update_scoreboard(score, length + i, spec + (i * p->specificity), p->exten, '.', callerid, p->deleted, p);
1918 ast_debug(4,"return because scoreboard has a match with '/'--- %s\n", score->exten->exten);
1919 return; /* the first match is all we need */
1922 if (p->next_char && p->next_char->x[0] == '/' && p->next_char->x[1] == 0) {
1923 new_find_extension("/", score, p->next_char, length + i, spec+(p->specificity*i), callerid, label, action);
1924 if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
1925 ast_debug(4, "return because scoreboard has exact match OR CANMATCH/MATCHMORE & canmatch set--- %s\n", score->exten ? score->exten->exten : "NULL");
1926 return; /* the first match is all we need */
1929 } else if (p->x[0] == '!' && p->x[1] == 0) {
1930 /* how many chars will the . match against? */
1932 const char *str2 = str;
1933 while (*str2 && *str2 != '/') {
1937 if (p->exten && *str2 != '/') {
1938 update_scoreboard(score, length + 1, spec + (p->specificity * i), p->exten, '!', callerid, p->deleted, p);
1940 ast_debug(4, "return because scoreboard has a '!' match--- %s\n", score->exten->exten);
1941 return; /* the first match is all we need */
1944 if (p->next_char && p->next_char->x[0] == '/' && p->next_char->x[1] == 0) {
1945 new_find_extension("/", score, p->next_char, length + i, spec + (p->specificity * i), callerid, label, action);
1946 if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
1947 ast_debug(4, "return because scoreboard has exact match OR CANMATCH/MATCHMORE & canmatch set with '/' and '!'--- %s\n", score->exten ? score->exten->exten : "NULL");
1948 return; /* the first match is all we need */
1951 } else if (p->x[0] == '/' && p->x[1] == 0) {
1952 /* the pattern in the tree includes the cid match! */
1953 if (p->next_char && callerid && *callerid) {
1954 new_find_extension(callerid, score, p->next_char, length + 1, spec, callerid, label, action);
1955 if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
1956 ast_debug(4, "return because scoreboard has exact match OR CANMATCH/MATCHMORE & canmatch set with '/'--- %s\n", score->exten ? score->exten->exten : "NULL");
1957 return; /* the first match is all we need */
1960 } else if (strchr(p->x, *str)) {
1961 ast_debug(4, "Nothing strange about this match\n");
1962 NEW_MATCHER_CHK_MATCH;
1963 NEW_MATCHER_RECURSE;
1965 } else if (strchr(p->x, *str)) {
1966 ast_debug(4, "Nothing strange about this match\n");
1967 NEW_MATCHER_CHK_MATCH;
1968 NEW_MATCHER_RECURSE;
1971 ast_debug(4, "return at end of func\n");
1974 /* the algorithm for forming the extension pattern tree is also a bit simple; you
1975 * traverse all the extensions in a context, and for each char of the extension,
1976 * you see if it exists in the tree; if it doesn't, you add it at the appropriate
1977 * spot. What more can I say? At the end of each exten, you cap it off by adding the
1978 * address of the extension involved. Duplicate patterns will be complained about.
1980 * Ideally, this would be done for each context after it is created and fully
1981 * filled. It could be done as a finishing step after extensions.conf or .ael is
1982 * loaded, or it could be done when the first search is encountered. It should only
1983 * have to be done once, until the next unload or reload.
1985 * I guess forming this pattern tree would be analogous to compiling a regex. Except
1986 * that a regex only handles 1 pattern, really. This trie holds any number
1987 * of patterns. Well, really, it **could** be considered a single pattern,
1988 * where the "|" (or) operator is allowed, I guess, in a way, sort of...
1991 static struct match_char *already_in_tree(struct match_char *current, char *pat, int is_pattern)
1993 struct match_char *t;
1999 for (t = current; t; t = t->alt_char) {
2000 if (is_pattern == t->is_pattern && !strcmp(pat, t->x)) {/* uh, we may want to sort exploded [] contents to make matching easy */
2008 /* The first arg is the location of the tree ptr, or the
2009 address of the next_char ptr in the node, so we can mess
2010 with it, if we need to insert at the beginning of the list */
2012 static void insert_in_next_chars_alt_char_list(struct match_char **parent_ptr, struct match_char *node)
2014 struct match_char *curr, *lcurr;
2016 /* insert node into the tree at "current", so the alt_char list from current is
2017 sorted in increasing value as you go to the leaves */
2018 if (!(*parent_ptr)) {
2023 if ((*parent_ptr)->specificity > node->specificity) {
2024 /* insert at head */
2025 node->alt_char = (*parent_ptr);
2030 lcurr = *parent_ptr;
2031 for (curr = (*parent_ptr)->alt_char; curr; curr = curr->alt_char) {
2032 if (curr->specificity > node->specificity) {
2033 node->alt_char = curr;
2034 lcurr->alt_char = node;
2041 lcurr->alt_char = node;
2046 struct pattern_node {
2047 /*! Pattern node specificity */
2049 /*! Pattern node match characters. */
2053 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)
2055 struct match_char *m;
2057 if (!(m = ast_calloc(1, sizeof(*m) + strlen(pattern->buf)))) {
2061 /* strcpy is safe here since we know its size and have allocated
2062 * just enough space for when we allocated m
2064 strcpy(m->x, pattern->buf);
2066 /* the specificity scores are the same as used in the old
2068 m->is_pattern = is_pattern;
2069 if (pattern->specif == 1 && is_pattern && pattern->buf[0] == 'N') {
2070 m->specificity = 0x0832;
2071 } else if (pattern->specif == 1 && is_pattern && pattern->buf[0] == 'Z') {
2072 m->specificity = 0x0931;
2073 } else if (pattern->specif == 1 && is_pattern && pattern->buf[0] == 'X') {
2074 m->specificity = 0x0a30;
2075 } else if (pattern->specif == 1 && is_pattern && pattern->buf[0] == '.') {
2076 m->specificity = 0x18000;
2077 } else if (pattern->specif == 1 && is_pattern && pattern->buf[0] == '!') {
2078 m->specificity = 0x28000;
2080 m->specificity = pattern->specif;
2083 if (!con->pattern_tree) {
2084 insert_in_next_chars_alt_char_list(&con->pattern_tree, m);
2086 if (already) { /* switch to the new regime (traversing vs appending)*/
2087 insert_in_next_chars_alt_char_list(nextcharptr, m);
2089 insert_in_next_chars_alt_char_list(¤t->next_char, m);
2098 * \brief Extract the next exten pattern node.
2100 * \param node Pattern node to fill.
2101 * \param src Next source character to read.
2102 * \param pattern TRUE if the exten is a pattern.
2103 * \param extenbuf Original exten buffer to use in diagnostic messages.
2105 * \retval Ptr to next extenbuf pos to read.
2107 static const char *get_pattern_node(struct pattern_node *node, const char *src, int pattern, const char *extenbuf)
2109 #define INC_DST_OVERFLOW_CHECK \
2111 if (dst - node->buf < sizeof(node->buf) - 1) { \
2119 node->buf[0] = '\0';
2121 if (*src == '[' && pattern) {
2122 char *dst = node->buf;
2123 const char *src_next;
2127 /* get past the '[' */
2131 /* Escaped character. */
2133 if (*src == '[' || *src == '\\' || *src == '-' || *src == ']') {
2135 INC_DST_OVERFLOW_CHECK;
2137 } else if (*src == '-') {
2138 unsigned char first;
2142 first = *(src_next - 1);
2146 /* Escaped character. */
2150 /* Possible char range. */
2151 if (node->buf[0] && last) {
2152 /* Expand the char range. */
2153 while (++first <= last) {
2155 INC_DST_OVERFLOW_CHECK;
2160 * There was no left or right char for the range.
2164 INC_DST_OVERFLOW_CHECK;
2166 } else if (*src == '\0') {
2167 ast_log(LOG_WARNING,
2168 "A matching ']' was not found for '[' in exten pattern '%s'\n",
2171 } else if (*src == ']') {
2176 INC_DST_OVERFLOW_CHECK;
2179 /* null terminate the exploded range */
2184 "Expanded character set too large to deal with in exten pattern '%s'. Ignoring character set.\n",
2186 node->buf[0] = '\0';
2190 /* Sort the characters in character set. */
2191 length = strlen(node->buf);
2193 ast_log(LOG_WARNING, "Empty character set in exten pattern '%s'. Ignoring.\n",
2195 node->buf[0] = '\0';
2198 qsort(node->buf, length, 1, compare_char);
2200 /* Remove duplicate characters from character set. */
2202 src_next = node->buf;
2203 while (*src_next++) {
2204 if (*dst != *src_next) {
2209 length = strlen(node->buf);
2211 node->specif = length | (unsigned char) node->buf[0];
2213 } else if (*src == '-') {
2214 /* Skip dashes in all extensions. */
2219 * XXX The escape character here does not remove any special
2220 * meaning to characters except the '[', '\\', and '-'
2221 * characters since they are special only in this function.
2223 node->buf[0] = *++src;
2224 if (!node->buf[0]) {
2228 node->buf[0] = *src;
2230 /* make sure n,x,z patterns are canonicalized to N,X,Z */
2231 if (node->buf[0] == 'n') {
2233 } else if (node->buf[0] == 'x') {
2235 } else if (node->buf[0] == 'z') {
2240 node->buf[1] = '\0';
2248 #undef INC_DST_OVERFLOW_CHECK
2251 static struct match_char *add_exten_to_pattern_tree(struct ast_context *con, struct ast_exten *e1, int findonly)
2253 struct match_char *m1 = NULL;
2254 struct match_char *m2 = NULL;
2255 struct match_char **m0;
2262 struct pattern_node pat_node[2];
2265 if (sizeof(extenbuf) < strlen(e1->exten) + strlen(e1->cidmatch) + 2) {
2267 "The pattern %s/%s is too big to deal with: it will be ignored! Disaster!\n",
2268 e1->exten, e1->cidmatch);
2271 sprintf(extenbuf, "%s/%s", e1->exten, e1->cidmatch);/* Safe. We just checked. */
2273 ast_copy_string(extenbuf, e1->exten, sizeof(extenbuf));
2277 ast_debug(1, "Adding exten %s to tree\n", extenbuf);
2279 m1 = con->pattern_tree; /* each pattern starts over at the root of the pattern tree */
2280 m0 = &con->pattern_tree;
2289 pos = get_pattern_node(&pat_node[idx_cur], pos, pattern, extenbuf);
2290 for (; pat_node[idx_cur].buf[0]; idx_cur = idx_next) {
2291 idx_next = (idx_cur + 1) % ARRAY_LEN(pat_node);
2292 pos = get_pattern_node(&pat_node[idx_next], pos, pattern, extenbuf);
2294 /* See about adding node to tree. */
2296 if (already && (m2 = already_in_tree(m1, pat_node[idx_cur].buf, pattern))
2298 if (!pat_node[idx_next].buf[0]) {
2300 * This is the end of the pattern, but not the end of the tree.
2301 * Mark this node with the exten... a shorter pattern might win
2302 * if the longer one doesn't match.
2308 ast_log(LOG_WARNING, "Found duplicate exten. Had %s found %s\n",
2309 m2->deleted ? "(deleted/invalid)" : m2->exten->exten, e1->exten);
2314 m1 = m2->next_char; /* m1 points to the node to compare against */
2315 m0 = &m2->next_char; /* m0 points to the ptr that points to m1 */
2316 } else { /* not already OR not m2 OR nor m2->next_char */
2321 m1 = m2; /* while m0 stays the same */
2326 m1 = add_pattern_node(con, m1, &pat_node[idx_cur], pattern, already, m0);
2327 if (!m1) { /* m1 is the node just added */
2330 m0 = &m1->next_char;
2332 if (!pat_node[idx_next].buf[0]) {
2333 if (m2 && m2->exten) {
2334 ast_log(LOG_WARNING, "Found duplicate exten. Had %s found %s\n",
2335 m2->deleted ? "(deleted/invalid)" : m2->exten->exten, e1->exten);
2341 /* The 'already' variable is a mini-optimization designed to make it so that we
2342 * don't have to call already_in_tree when we know it will return false.
2350 static void create_match_char_tree(struct ast_context *con)
2352 struct ast_hashtab_iter *t1;
2353 struct ast_exten *e1;
2355 int biggest_bucket, resizes, numobjs, numbucks;
2357 ast_debug(1, "Creating Extension Trie for context %s(%p)\n", con->name, con);
2358 ast_hashtab_get_stats(con->root_table, &biggest_bucket, &resizes, &numobjs, &numbucks);
2359 ast_debug(1, "This tree has %d objects in %d bucket lists, longest list=%d objects, and has resized %d times\n",
2360 numobjs, numbucks, biggest_bucket, resizes);
2362 t1 = ast_hashtab_start_traversal(con->root_table);
2363 while ((e1 = ast_hashtab_next(t1))) {
2365 add_exten_to_pattern_tree(con, e1, 0);
2367 ast_log(LOG_ERROR, "Attempt to create extension with no extension name.\n");
2370 ast_hashtab_end_traversal(t1);
2373 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! */
2375 /* destroy all the alternates */
2376 if (pattern_tree->alt_char) {
2377 destroy_pattern_tree(pattern_tree->alt_char);
2378 pattern_tree->alt_char = 0;
2380 /* destroy all the nexts */
2381 if (pattern_tree->next_char) {
2382 destroy_pattern_tree(pattern_tree->next_char);
2383 pattern_tree->next_char = 0;
2385 pattern_tree->exten = 0; /* never hurts to make sure there's no pointers laying around */
2386 ast_free(pattern_tree);
2390 * Special characters used in patterns:
2391 * '_' underscore is the leading character of a pattern.
2392 * In other position it is treated as a regular char.
2393 * . one or more of any character. Only allowed at the end of
2395 * ! zero or more of anything. Also impacts the result of CANMATCH
2396 * and MATCHMORE. Only allowed at the end of a pattern.
2397 * In the core routine, ! causes a match with a return code of 2.
2398 * In turn, depending on the search mode: (XXX check if it is implemented)
2399 * - E_MATCH retuns 1 (does match)
2400 * - E_MATCHMORE returns 0 (no match)
2401 * - E_CANMATCH returns 1 (does match)
2403 * / should not appear as it is considered the separator of the CID info.
2404 * XXX at the moment we may stop on this char.
2406 * X Z N match ranges 0-9, 1-9, 2-9 respectively.
2407 * [ denotes the start of a set of character. Everything inside
2408 * is considered literally. We can have ranges a-d and individual
2409 * characters. A '[' and '-' can be considered literally if they
2410 * are just before ']'.
2411 * XXX currently there is no way to specify ']' in a range, nor \ is
2412 * considered specially.
2414 * When we compare a pattern with a specific extension, all characters in the extension
2415 * itself are considered literally.
2416 * XXX do we want to consider space as a separator as well ?
2417 * XXX do we want to consider the separators in non-patterns as well ?
2421 * \brief helper functions to sort extensions and patterns in the desired way,
2422 * so that more specific patterns appear first.
2424 * ext_cmp1 compares individual characters (or sets of), returning
2425 * an int where bits 0-7 are the ASCII code of the first char in the set,
2426 * while bit 8-15 are the cardinality of the set minus 1.
2427 * This way more specific patterns (smaller cardinality) appear first.
2428 * Wildcards have a special value, so that we can directly compare them to
2429 * sets by subtracting the two values. In particular:
2430 * 0x000xx one character, xx
2431 * 0x0yyxx yy character set starting with xx
2432 * 0x10000 '.' (one or more of anything)
2433 * 0x20000 '!' (zero or more of anything)
2434 * 0x30000 NUL (end of string)
2435 * 0x40000 error in set.
2436 * The pointer to the string is advanced according to needs.
2438 * 1. the empty set is equivalent to NUL.
2439 * 2. given that a full set has always 0 as the first element,
2440 * we could encode the special cases as 0xffXX where XX
2441 * is 1, 2, 3, 4 as used above.
2443 static int ext_cmp1(const char **p, unsigned char *bitwise)
2445 int c, cmin = 0xff, count = 0;
2448 /* load value and advance pointer */
2451 /* always return unless we have a set of chars */
2452 switch (toupper(c)) {
2453 default: /* ordinary character */
2454 bitwise[c / 8] = 1 << (c % 8);
2455 return 0x0100 | (c & 0xff);
2457 case 'N': /* 2..9 */
2460 return 0x0800 | '2';
2462 case 'X': /* 0..9 */
2465 return 0x0A00 | '0';
2467 case 'Z': /* 1..9 */
2470 return 0x0900 | '1';
2472 case '.': /* wildcard */
2475 case '!': /* earlymatch */
2476 return 0x28000; /* less specific than NULL */
2478 case '\0': /* empty string */
2482 case '[': /* pattern */
2485 /* locate end of set */
2486 end = strchr(*p, ']');
2489 ast_log(LOG_WARNING, "Wrong usage of [] in the extension\n");
2490 return 0x40000; /* XXX make this entry go last... */
2493 for (; *p < end ; (*p)++) {
2494 unsigned char c1, c2; /* first-last char in range */
2495 c1 = (unsigned char)((*p)[0]);
2496 if (*p + 2 < end && (*p)[1] == '-') { /* this is a range */
2497 c2 = (unsigned char)((*p)[2]);
2498 *p += 2; /* skip a total of 3 chars */
2499 } else { /* individual character */
2505 for (; c1 <= c2; c1++) {
2506 unsigned char mask = 1 << (c1 % 8);
2507 /*!\note If two patterns score the same, the one with the lowest
2508 * ascii values will compare as coming first. */
2509 /* Flag the character as included (used) and count it. */
2510 if (!(bitwise[ c1 / 8 ] & mask)) {
2511 bitwise[ c1 / 8 ] |= mask;
2517 return count == 0 ? 0x30000 : (count | cmin);
2521 * \brief the full routine to compare extensions in rules.
2523 static int ext_cmp(const char *a, const char *b)
2525 /* make sure non-patterns come first.
2526 * If a is not a pattern, it either comes first or
2527 * we do a more complex pattern comparison.
2532 return (b[0] == '_') ? -1 : strcmp(a, b);
2534 /* Now we know a is a pattern; if b is not, a comes first */
2538 /* ok we need full pattern sorting routine.
2539 * skip past the underscores */
2542 unsigned char bitwise[2][32] = { { 0, } };
2543 ret = ext_cmp1(&a, bitwise[0]) - ext_cmp1(&b, bitwise[1]);
2545 /* Are the classes different, even though they score the same? */
2546 ret = memcmp(bitwise[0], bitwise[1], 32);
2548 } while (!ret && a && b);
2552 return (ret > 0) ? 1 : -1;
2556 int ast_extension_cmp(const char *a, const char *b)
2558 return ext_cmp(a, b);
2563 * \brief used ast_extension_{match|close}
2564 * mode is as follows:
2565 * E_MATCH success only on exact match
2566 * E_MATCHMORE success only on partial match (i.e. leftover digits in pattern)
2567 * E_CANMATCH either of the above.
2568 * \retval 0 on no-match
2569 * \retval 1 on match
2570 * \retval 2 on early match.
2573 static int _extension_match_core(const char *pattern, const char *data, enum ext_match_t mode)
2575 mode &= E_MATCH_MASK; /* only consider the relevant bits */
2577 #ifdef NEED_DEBUG_HERE
2578 ast_log(LOG_NOTICE,"match core: pat: '%s', dat: '%s', mode=%d\n", pattern, data, (int)mode);
2581 if ( (mode == E_MATCH) && (pattern[0] == '_') && (!strcasecmp(pattern,data)) ) { /* note: if this test is left out, then _x. will not match _x. !!! */
2582 #ifdef NEED_DEBUG_HERE
2583 ast_log(LOG_NOTICE,"return (1) - pattern matches pattern\n");
2588 if (pattern[0] != '_') { /* not a pattern, try exact or partial match */
2589 int ld = strlen(data), lp = strlen(pattern);
2591 if (lp < ld) { /* pattern too short, cannot match */
2592 #ifdef NEED_DEBUG_HERE
2593 ast_log(LOG_NOTICE,"return (0) - pattern too short, cannot match\n");
2597 /* depending on the mode, accept full or partial match or both */
2598 if (mode == E_MATCH) {
2599 #ifdef NEED_DEBUG_HERE
2600 ast_log(LOG_NOTICE,"return (!strcmp(%s,%s) when mode== E_MATCH)\n", pattern, data);
2602 return !strcmp(pattern, data); /* 1 on match, 0 on fail */
2604 if (ld == 0 || !strncasecmp(pattern, data, ld)) { /* partial or full match */
2605 #ifdef NEED_DEBUG_HERE
2606 ast_log(LOG_NOTICE,"return (mode(%d) == E_MATCHMORE ? lp(%d) > ld(%d) : 1)\n", mode, lp, ld);
2608 return (mode == E_MATCHMORE) ? lp > ld : 1; /* XXX should consider '!' and '/' ? */
2610 #ifdef NEED_DEBUG_HERE
2611 ast_log(LOG_NOTICE,"return (0) when ld(%d) > 0 && pattern(%s) != data(%s)\n", ld, pattern, data);
2616 pattern++; /* skip leading _ */
2618 * XXX below we stop at '/' which is a separator for the CID info. However we should
2619 * not store '/' in the pattern at all. When we insure it, we can remove the checks.
2621 while (*data && *pattern && *pattern != '/') {
2624 if (*data == '-') { /* skip '-' in data (just a separator) */
2628 switch (toupper(*pattern)) {
2629 case '[': /* a range */
2630 end = strchr(pattern+1, ']'); /* XXX should deal with escapes ? */
2632 ast_log(LOG_WARNING, "Wrong usage of [] in the extension\n");
2633 return 0; /* unconditional failure */
2635 for (pattern++; pattern != end; pattern++) {
2636 if (pattern+2 < end && pattern[1] == '-') { /* this is a range */
2637 if (*data >= pattern[0] && *data <= pattern[2])
2638 break; /* match found */
2640 pattern += 2; /* skip a total of 3 chars */
2643 } else if (*data == pattern[0])
2644 break; /* match found */
2646 if (pattern == end) {
2647 #ifdef NEED_DEBUG_HERE
2648 ast_log(LOG_NOTICE,"return (0) when pattern==end\n");
2652 pattern = end; /* skip and continue */
2655 if (*data < '2' || *data > '9') {
2656 #ifdef NEED_DEBUG_HERE
2657 ast_log(LOG_NOTICE,"return (0) N is matched\n");
2663 if (*data < '0' || *data > '9') {
2664 #ifdef NEED_DEBUG_HERE
2665 ast_log(LOG_NOTICE,"return (0) X is matched\n");
2671 if (*data < '1' || *data > '9') {
2672 #ifdef NEED_DEBUG_HERE
2673 ast_log(LOG_NOTICE,"return (0) Z is matched\n");
2678 case '.': /* Must match, even with more digits */
2679 #ifdef NEED_DEBUG_HERE
2680 ast_log(LOG_NOTICE, "return (1) when '.' is matched\n");
2683 case '!': /* Early match */
2684 #ifdef NEED_DEBUG_HERE
2685 ast_log(LOG_NOTICE, "return (2) when '!' is matched\n");
2689 case '-': /* Ignore these in patterns */
2690 data--; /* compensate the final data++ */
2693 if (*data != *pattern) {
2694 #ifdef NEED_DEBUG_HERE
2695 ast_log(LOG_NOTICE, "return (0) when *data(%c) != *pattern(%c)\n", *data, *pattern);
2703 if (*data) /* data longer than pattern, no match */ {
2704 #ifdef NEED_DEBUG_HERE
2705 ast_log(LOG_NOTICE, "return (0) when data longer than pattern\n");
2711 * match so far, but ran off the end of the data.
2712 * Depending on what is next, determine match or not.
2714 if (*pattern == '\0' || *pattern == '/') { /* exact match */
2715 #ifdef NEED_DEBUG_HERE
2716 ast_log(LOG_NOTICE, "at end, return (%d) in 'exact match'\n", (mode==E_MATCHMORE) ? 0 : 1);
2718 return (mode == E_MATCHMORE) ? 0 : 1; /* this is a failure for E_MATCHMORE */
2719 } else if (*pattern == '!') { /* early match */
2720 #ifdef NEED_DEBUG_HERE
2721 ast_log(LOG_NOTICE, "at end, return (2) when '!' is matched\n");
2724 } else { /* partial match */
2725 #ifdef NEED_DEBUG_HERE
2726 ast_log(LOG_NOTICE, "at end, return (%d) which deps on E_MATCH\n", (mode == E_MATCH) ? 0 : 1);
2728 return (mode == E_MATCH) ? 0 : 1; /* this is a failure for E_MATCH */
2733 * Wrapper around _extension_match_core() to do performance measurement
2734 * using the profiling code.
2736 static int extension_match_core(const char *pattern, const char *data, enum ext_match_t mode)
2739 static int prof_id = -2; /* marker for 'unallocated' id */
2740 if (prof_id == -2) {
2741 prof_id = ast_add_profile("ext_match", 0);
2743 ast_mark(prof_id, 1);
2744 i = _extension_match_core(ast_strlen_zero(pattern) ? "" : pattern, ast_strlen_zero(data) ? "" : data, mode);
2745 ast_mark(prof_id, 0);
2749 int ast_extension_match(const char *pattern, const char *data)
2751 return extension_match_core(pattern, data, E_MATCH);
2754 int ast_extension_close(const char *pattern, const char *data, int needmore)
2756 if (needmore != E_MATCHMORE && needmore != E_CANMATCH)
2757 ast_log(LOG_WARNING, "invalid argument %d\n", needmore);
2758 return extension_match_core(pattern, data, needmore);
2761 struct fake_context /* this struct is purely for matching in the hashtab */
2764 struct ast_exten *root;
2765 struct ast_hashtab *root_table;
2766 struct match_char *pattern_tree;
2767 struct ast_context *next;
2768 struct ast_include *includes;
2769 struct ast_ignorepat *ignorepats;
2770 const char *registrar;
2772 AST_LIST_HEAD_NOLOCK(, ast_sw) alts;
2773 ast_mutex_t macrolock;
2777 struct ast_context *ast_context_find(const char *name)
2779 struct ast_context *tmp;
2780 struct fake_context item;
2785 ast_rdlock_contexts();
2786 if (contexts_table) {
2787 ast_copy_string(item.name, name, sizeof(item.name));
2788 tmp = ast_hashtab_lookup(contexts_table, &item);
2791 while ((tmp = ast_walk_contexts(tmp))) {
2792 if (!strcasecmp(name, tmp->name)) {
2797 ast_unlock_contexts();
2801 #define STATUS_NO_CONTEXT 1
2802 #define STATUS_NO_EXTENSION 2
2803 #define STATUS_NO_PRIORITY 3
2804 #define STATUS_NO_LABEL 4
2805 #define STATUS_SUCCESS 5
2807 static int matchcid(const char *cidpattern, const char *callerid)
2809 /* If the Caller*ID pattern is empty, then we're matching NO Caller*ID, so
2810 failing to get a number should count as a match, otherwise not */
2812 if (ast_strlen_zero(callerid)) {
2813 return ast_strlen_zero(cidpattern) ? 1 : 0;
2816 return ast_extension_match(cidpattern, callerid);
2819 struct ast_exten *pbx_find_extension(struct ast_channel *chan,
2820 struct ast_context *bypass, struct pbx_find_info *q,
2821 const char *context, const char *exten, int priority,
2822 const char *label, const char *callerid, enum ext_match_t action)
2825 struct ast_context *tmp = NULL;
2826 struct ast_exten *e = NULL, *eroot = NULL;
2827 struct ast_include *i = NULL;
2828 struct ast_sw *sw = NULL;
2829 struct ast_exten pattern = {NULL, };
2830 struct scoreboard score = {0, };
2831 struct ast_str *tmpdata = NULL;
2833 pattern.label = label;
2834 pattern.priority = priority;
2835 #ifdef NEED_DEBUG_HERE
2836 ast_log(LOG_NOTICE, "Looking for cont/ext/prio/label/action = %s/%s/%d/%s/%d\n", context, exten, priority, label, (int) action);
2839 /* Initialize status if appropriate */
2840 if (q->stacklen == 0) {
2841 q->status = STATUS_NO_CONTEXT;
2844 q->foundcontext = NULL;
2845 } else if (q->stacklen >= AST_PBX_MAX_STACK) {
2846 ast_log(LOG_WARNING, "Maximum PBX stack exceeded\n");
2850 /* Check first to see if we've already been checked */
2851 for (x = 0; x < q->stacklen; x++) {
2852 if (!strcasecmp(q->incstack[x], context))
2856 if (bypass) { /* bypass means we only look there */
2858 } else { /* look in contexts */
2859 tmp = find_context(context);
2865 if (q->status < STATUS_NO_EXTENSION)
2866 q->status = STATUS_NO_EXTENSION;
2868 /* Do a search for matching extension */
2871 score.total_specificity = 0;
2873 score.total_length = 0;
2874 if (!tmp->pattern_tree && tmp->root_table) {
2875 create_match_char_tree(tmp);
2877 ast_debug(1, "Tree Created in context %s:\n", context);
2878 log_match_char_tree(tmp->pattern_tree," ");
2882 ast_log(LOG_NOTICE, "The Trie we are searching in:\n");
2883 log_match_char_tree(tmp->pattern_tree, ":: ");
2887 if (!ast_strlen_zero(overrideswitch)) {
2888 char *osw = ast_strdupa(overrideswitch), *name;
2889 struct ast_switch *asw;
2890 ast_switch_f *aswf = NULL;
2894 name = strsep(&osw, "/");
2895 asw = pbx_findswitch(name);
2898 ast_log(LOG_WARNING, "No such switch '%s'\n", name);
projects / asterisk/asterisk.git / blob