From 01d3fd2167cba91a2a56902b082153f08b921248 Mon Sep 17 00:00:00 2001 From: Richard Mudgett Date: Fri, 9 Dec 2011 01:33:29 +0000 Subject: Fix some parsing issues in add_exten_to_pattern_tree(). * Simplify compare_char() and avoid potential sign extension issue. * Fix infinite loop in add_exten_to_pattern_tree() handling of character set escape handling. * Added buffer overflow checks in add_exten_to_pattern_tree() character set collection. * Made ignore empty character sets. * Added escape character handling to end-of-range character in character sets. This has a slight change in behavior if the end-of-range character is an escape character. You must now escape it. * Fix potential sign extension issue when expanding character set ranges. * Made remove duplicated characters from character sets. The duplicate characters lower extension matching priority and prevent duplicate extension detection. * Fix escape character handling when the escape character is trying to escape the end-of-string. We could have continued processing characters after the end of the exten string. We could have added the previous character to the pattern matching tree incorrectly. (closes issue ASTERISK-18909) Reported by: Luke-Jr ........ Merged revisions 347811 from http://svn.asterisk.org/svn/asterisk/branches/1.8 ........ Merged revisions 347812 from http://svn.asterisk.org/svn/asterisk/branches/10 git-svn-id: https://origsvn.digium.com/svn/asterisk/trunk@347813 65c4cc65-6c06-0410-ace0-fbb531ad65f3 --- main/pbx.c | 345 +++++++++++++++++++++++++++++++++++++++++-------------------- 1 file changed, 233 insertions(+), 112 deletions(-) diff --git a/main/pbx.c b/main/pbx.c index ff0190968..fc4b3d93a 100644 --- a/main/pbx.c +++ b/main/pbx.c @@ -1138,9 +1138,6 @@ static void new_find_extension(const char *str, struct scoreboard *score, static struct match_char *already_in_tree(struct match_char *current, char *pat, int is_pattern); static struct match_char *add_exten_to_pattern_tree(struct ast_context *con, struct ast_exten *e1, int findonly); -static struct match_char *add_pattern_node(struct ast_context *con, - struct match_char *current, char *pattern, int is_pattern, - int already, int specificity, struct match_char **parent); static void create_match_char_tree(struct ast_context *con); static struct ast_exten *get_canmatch_exten(struct match_char *node); static void destroy_pattern_tree(struct match_char *pattern_tree); @@ -1161,17 +1158,23 @@ static int ast_add_extension2_lockopt(struct ast_context *con, static struct ast_context *find_context_locked(const char *context); static struct ast_context *find_context(const char *context); -/* a func for qsort to use to sort a char array */ +/*! + * \internal + * \brief Character array comparison function for qsort. + * + * \param a Left side object. + * \param b Right side object. + * + * \retval <0 if a < b + * \retval =0 if a = b + * \retval >0 if a > b + */ static int compare_char(const void *a, const void *b) { - const char *ac = a; - const char *bc = b; - if ((*ac) < (*bc)) - return -1; - else if ((*ac) == (*bc)) - return 0; - else - return 1; + const unsigned char *ac = a; + const unsigned char *bc = b; + + return *ac - *bc; } /* labels, contexts are case sensitive priority numbers are ints */ @@ -2035,34 +2038,42 @@ static void insert_in_next_chars_alt_char_list(struct match_char **parent_ptr, s } -static struct match_char *add_pattern_node(struct ast_context *con, struct match_char *current, char *pattern, int is_pattern, int already, int specificity, struct match_char **nextcharptr) +struct pattern_node { + /*! Pattern node specificity */ + int specif; + /*! Pattern node match characters. */ + char buf[256]; +}; + +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) { struct match_char *m; - - if (!(m = ast_calloc(1, sizeof(*m) + strlen(pattern)))) { + + if (!(m = ast_calloc(1, sizeof(*m) + strlen(pattern->buf)))) { return NULL; } /* strcpy is safe here since we know its size and have allocated * just enough space for when we allocated m */ - strcpy(m->x, pattern); + strcpy(m->x, pattern->buf); /* the specificity scores are the same as used in the old pattern matcher. */ m->is_pattern = is_pattern; - if (specificity == 1 && is_pattern && pattern[0] == 'N') + if (pattern->specif == 1 && is_pattern && pattern->buf[0] == 'N') { m->specificity = 0x0832; - else if (specificity == 1 && is_pattern && pattern[0] == 'Z') + } else if (pattern->specif == 1 && is_pattern && pattern->buf[0] == 'Z') { m->specificity = 0x0931; - else if (specificity == 1 && is_pattern && pattern[0] == 'X') + } else if (pattern->specif == 1 && is_pattern && pattern->buf[0] == 'X') { m->specificity = 0x0a30; - else if (specificity == 1 && is_pattern && pattern[0] == '.') + } else if (pattern->specif == 1 && is_pattern && pattern->buf[0] == '.') { m->specificity = 0x18000; - else if (specificity == 1 && is_pattern && pattern[0] == '!') + } else if (pattern->specif == 1 && is_pattern && pattern->buf[0] == '!') { m->specificity = 0x28000; - else - m->specificity = specificity; + } else { + m->specificity = pattern->specif; + } if (!con->pattern_tree) { insert_in_next_chars_alt_char_list(&con->pattern_tree, m); @@ -2077,111 +2088,220 @@ static struct match_char *add_pattern_node(struct ast_context *con, struct match return m; } -static struct match_char *add_exten_to_pattern_tree(struct ast_context *con, struct ast_exten *e1, int findonly) -{ - struct match_char *m1 = NULL, *m2 = NULL, **m0; - int specif; - int already; - int pattern = 0; - char buf[256]; - char extenbuf[512]; - char *s1 = extenbuf; - int l1 = strlen(e1->exten) + strlen(e1->cidmatch) + 2; - +/*! + * \internal + * \brief Extract the next exten pattern node. + * + * \param node Pattern node to fill. + * \param src Next source character to read. + * \param pattern TRUE if the exten is a pattern. + * \param extenbuf Original exten buffer to use in diagnostic messages. + * + * \retval Ptr to next extenbuf pos to read. + */ +static const char *get_pattern_node(struct pattern_node *node, const char *src, int pattern, const char *extenbuf) +{ +#define INC_DST_OVERFLOW_CHECK \ + do { \ + if (dst - node->buf < sizeof(node->buf) - 1) { \ + ++dst; \ + } else { \ + overflow = 1; \ + } \ + } while (0) + + node->specif = 0; + node->buf[0] = '\0'; + while (*src) { + if (*src == '[' && pattern) { + char *dst = node->buf; + const char *src_next; + int length; + int overflow = 0; + + /* get past the '[' */ + ++src; + for (;;) { + if (*src == '\\') { + /* Escaped character. */ + ++src; + if (*src == '[' || *src == '\\' || *src == '-' || *src == ']') { + *dst = *src++; + INC_DST_OVERFLOW_CHECK; + } + } else if (*src == '-') { + unsigned char first; + unsigned char last; - ast_copy_string(extenbuf, e1->exten, sizeof(extenbuf)); + src_next = src; + first = *(src_next - 1); + last = *++src_next; - if (e1->matchcid && l1 <= sizeof(extenbuf)) { - strcat(extenbuf, "/"); - strcat(extenbuf, e1->cidmatch); - } else if (l1 > sizeof(extenbuf)) { - ast_log(LOG_ERROR, "The pattern %s/%s is too big to deal with: it will be ignored! Disaster!\n", e1->exten, e1->cidmatch); - return 0; - } -#ifdef NEED_DEBUG - ast_debug(1, "Adding exten %s%c%s to tree\n", s1, e1->matchcid ? '/' : ' ', e1->matchcid ? e1->cidmatch : ""); -#endif - m1 = con->pattern_tree; /* each pattern starts over at the root of the pattern tree */ - m0 = &con->pattern_tree; - already = 1; - - if ( *s1 == '_') { - pattern = 1; - s1++; - } - while (*s1) { - if (pattern && *s1 == '[' && *(s1 - 1) != '\\') { - char *s2 = buf; - buf[0] = 0; - s1++; /* get past the '[' */ - while (*s1 != ']' && *(s1 - 1) != '\\') { - if (*s1 == '\\') { - if (*(s1 + 1) == ']') { - *s2++ = ']'; - s1 += 2; - } else if (*(s1 + 1) == '\\') { - *s2++ = '\\'; - s1 += 2; - } else if (*(s1 + 1) == '-') { - *s2++ = '-'; - s1 += 2; - } else if (*(s1 + 1) == '[') { - *s2++ = '['; - s1 += 2; + if (last == '\\') { + /* Escaped character. */ + last = *++src_next; } - } else if (*s1 == '-') { /* remember to add some error checking to all this! */ - char s3 = *(s1 - 1); - char s4 = *(s1 + 1); - for (s3++; s3 <= s4; s3++) { - *s2++ = s3; + + /* Possible char range. */ + if (node->buf[0] && last) { + /* Expand the char range. */ + while (++first <= last) { + *dst = first; + INC_DST_OVERFLOW_CHECK; + } + src = src_next + 1; + } else { + /* + * There was no left or right char for the range. + * It is just a '-'. + */ + *dst = *src++; + INC_DST_OVERFLOW_CHECK; } - s1 += 2; - } else if (*s1 == '\0') { - ast_log(LOG_WARNING, "A matching ']' was not found for '[' in pattern string '%s'\n", extenbuf); + } else if (*src == '\0') { + ast_log(LOG_WARNING, + "A matching ']' was not found for '[' in exten pattern '%s'\n", + extenbuf); + break; + } else if (*src == ']') { + ++src; break; } else { - *s2++ = *s1++; + *dst = *src++; + INC_DST_OVERFLOW_CHECK; } } - *s2 = 0; /* null terminate the exploded range */ - /* sort the characters */ + /* null terminate the exploded range */ + *dst = '\0'; - specif = strlen(buf); - qsort(buf, specif, 1, compare_char); - specif <<= 8; - specif += buf[0]; - } else if (*s1 == '-') { - /* Skip dashes in patterns */ - s1++; - continue; + if (overflow) { + ast_log(LOG_ERROR, + "Expanded character set too large to deal with in exten pattern '%s'. Ignoring character set.\n", + extenbuf); + node->buf[0] = '\0'; + continue; + } + + /* Sort the characters in character set. */ + length = strlen(node->buf); + if (!length) { + ast_log(LOG_WARNING, "Empty character set in exten pattern '%s'. Ignoring.\n", + extenbuf); + node->buf[0] = '\0'; + continue; + } + qsort(node->buf, length, 1, compare_char); + + /* Remove duplicate characters from character set. */ + dst = node->buf; + src_next = node->buf; + while (*src_next++) { + if (*dst != *src_next) { + *++dst = *src_next; + } + } + + length = strlen(node->buf); + length <<= 8; + node->specif = length | (unsigned char) node->buf[0]; + break; + } else if (*src == '-') { + /* Skip dashes in all extensions. */ + ++src; } else { - if (*s1 == '\\') { - s1++; - buf[0] = *s1; + if (*src == '\\') { + /* + * XXX The escape character here does not remove any special + * meaning to characters except the '[', '\\', and '-' + * characters since they are special only in this function. + */ + node->buf[0] = *++src; + if (!node->buf[0]) { + break; + } } else { + node->buf[0] = *src; if (pattern) { - if (*s1 == 'n') { /* make sure n,x,z patterns are canonicalized to N,X,Z */ - *s1 = 'N'; - } else if (*s1 == 'x') { - *s1 = 'X'; - } else if (*s1 == 'z') { - *s1 = 'Z'; + /* make sure n,x,z patterns are canonicalized to N,X,Z */ + if (node->buf[0] == 'n') { + node->buf[0] = 'N'; + } else if (node->buf[0] == 'x') { + node->buf[0] = 'X'; + } else if (node->buf[0] == 'z') { + node->buf[0] = 'Z'; } } - buf[0] = *s1; } - buf[1] = 0; - specif = 1; + node->buf[1] = '\0'; + node->specif = 1; + ++src; + break; + } + } + return src; + +#undef INC_DST_OVERFLOW_CHECK +} + +static struct match_char *add_exten_to_pattern_tree(struct ast_context *con, struct ast_exten *e1, int findonly) +{ + struct match_char *m1 = NULL; + struct match_char *m2 = NULL; + struct match_char **m0; + const char *pos; + int already; + int pattern = 0; + int idx_cur; + int idx_next; + char extenbuf[512]; + struct pattern_node pat_node[2]; + + if (e1->matchcid) { + if (sizeof(extenbuf) < strlen(e1->exten) + strlen(e1->cidmatch) + 2) { + ast_log(LOG_ERROR, + "The pattern %s/%s is too big to deal with: it will be ignored! Disaster!\n", + e1->exten, e1->cidmatch); + return NULL; } - m2 = 0; - if (already && (m2 = already_in_tree(m1, buf, pattern)) && m2->next_char) { - if (!(*(s1 + 1))) { /* if this is the end of the pattern, but not the end of the tree, then mark this node with the exten... - a shorter pattern might win if the longer one doesn't match */ + sprintf(extenbuf, "%s/%s", e1->exten, e1->cidmatch);/* Safe. We just checked. */ + } else { + ast_copy_string(extenbuf, e1->exten, sizeof(extenbuf)); + } + +#ifdef NEED_DEBUG + ast_debug(1, "Adding exten %s to tree\n", extenbuf); +#endif + m1 = con->pattern_tree; /* each pattern starts over at the root of the pattern tree */ + m0 = &con->pattern_tree; + already = 1; + + pos = extenbuf; + if (*pos == '_') { + pattern = 1; + ++pos; + } + idx_cur = 0; + pos = get_pattern_node(&pat_node[idx_cur], pos, pattern, extenbuf); + for (; pat_node[idx_cur].buf[0]; idx_cur = idx_next) { + idx_next = (idx_cur + 1) % ARRAY_LEN(pat_node); + pos = get_pattern_node(&pat_node[idx_next], pos, pattern, extenbuf); + + /* See about adding node to tree. */ + m2 = NULL; + if (already && (m2 = already_in_tree(m1, pat_node[idx_cur].buf, pattern)) + && m2->next_char) { + if (!pat_node[idx_next].buf[0]) { + /* + * This is the end of the pattern, but not the end of the tree. + * Mark this node with the exten... a shorter pattern might win + * if the longer one doesn't match. + */ if (findonly) { return m2; } if (m2->exten) { - ast_log(LOG_WARNING, "Found duplicate exten. Had %s found %s\n", m2->deleted ? "(deleted/invalid)" : m2->exten->exten, e1->exten); + ast_log(LOG_WARNING, "Found duplicate exten. Had %s found %s\n", + m2->deleted ? "(deleted/invalid)" : m2->exten->exten, e1->exten); } m2->exten = e1; m2->deleted = 0; @@ -2198,14 +2318,16 @@ static struct match_char *add_exten_to_pattern_tree(struct ast_context *con, str if (findonly) { return m1; } - if (!(m1 = add_pattern_node(con, m1, buf, pattern, already,specif, m0))) { /* m1 is the node just added */ + m1 = add_pattern_node(con, m1, &pat_node[idx_cur], pattern, already, m0); + if (!m1) { /* m1 is the node just added */ return NULL; } m0 = &m1->next_char; } - if (!(*(s1 + 1))) { + if (!pat_node[idx_next].buf[0]) { if (m2 && m2->exten) { - ast_log(LOG_WARNING, "Found duplicate exten. Had %s found %s\n", m2->deleted ? "(deleted/invalid)" : m2->exten->exten, e1->exten); + ast_log(LOG_WARNING, "Found duplicate exten. Had %s found %s\n", + m2->deleted ? "(deleted/invalid)" : m2->exten->exten, e1->exten); } m1->deleted = 0; m1->exten = e1; @@ -2216,7 +2338,6 @@ static struct match_char *add_exten_to_pattern_tree(struct ast_context *con, str */ already = 0; } - s1++; /* advance to next char */ } return m1; } -- cgit v1.2.3