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

1 files 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;
 }