dgaudet 98/03/12 23:11:03
Modified: src/main util_uri.c
Log:
Deal with the performance problem in parse_uri_components(). This new
version is over two orders of magnitude faster based on timing trials
requesting the test page from mod_test_util_uri. It's 50% faster overall
when doing a zb /index.html with the default index.html.
I'm still resiting the urge to hardcode i386 assembly language with
a C fallback for the rest of the world ;)
Revision Changes Path
1.9 +205 -191 apache-1.3/src/main/util_uri.c
Index: util_uri.c
===================================================================
RCS file: /export/home/cvs/apache-1.3/src/main/util_uri.c,v
retrieving revision 1.8
retrieving revision 1.9
diff -u -r1.8 -r1.9
--- util_uri.c 1998/03/07 21:39:28 1.8
+++ util_uri.c 1998/03/13 07:11:02 1.9
@@ -197,182 +197,15 @@
return ret;
}
-
-
-/* This will serve as the basis for an optimized parse_uri_components, sorry
- * about the if 0
+/* The regex version of parse_uri_components has the advantage that it is
+ * relatively easy to understand and extend. But it has the disadvantage
+ * that the regexes are complex enough that regex libraries really
+ * don't do a great job with them performancewise.
+ *
+ * The default is a hand coded scanner that is two orders of magnitude
+ * faster.
*/
-
-#if 0
-/* parse_uri_components():
- * Parse a given URI, fill in all supplied fields of a uri_components
- * structure. This eliminates the necessity of extracting host, port,
- * path, query info repeatedly in the modules.
- * Side effects:
- * - fills in fields of uri_components *uptr
- * - none on any of the r->* fields
- */
-API_EXPORT(int) parse_uri_components(pool *p, const char *uri,
uri_components *uptr)
-{
- const char *s;
- int ret = HTTP_OK;
-
- /* Initialize the structure. parse_uri() and parse_uri_components()
- * can be called more than once per request.
- */
- memset (uptr, '\0', sizeof(*uptr));
- uptr->is_initialized = 1;
-
- /* A proxy request contains a ':' early on (after the scheme),
- * but not as first character. RFC1738 allows [a-zA-Z0-9-+.]:
- */
- for (s = uri; s != '\0'; s++)
- if (!isalnum(*s) && *s != '+' && *s != '-' && *s != '.')
- break;
-
- if (s == uri || s[0] != ':' || s[1] == '\0') {
- /* not a full URL (not: scheme://host/path), so no proxy request: */
-
- /* Store path, without the optional "?query" argument: */
- uptr->path = getword (p, &uri, '?');
- if (uptr->path[0] == '\0') {
- uptr->path = NULL;
- }
-
- if (uri[0] != '\0') {
- uptr->query = pstrdup(p, uri);
- }
-
-#if defined(__EMX__) || defined(WIN32)
- /* Handle path translations for OS/2 and plug security hole.
- * This will prevent "http://www.wherever.com/..\..\/"; from
- * returning a directory for the root drive.
- */
- for (s = uptr->path; (s = strchr(s, '\\')) != NULL; )
- *(char *)s = '/';
-#ifndef WIN32 /* for OS/2 only: */
- /* Fix OS/2 HPFS filename case problem. */
- uptr->path = strlwr(uptr->path);
-#endif
-#endif /* __EMX__ || WIN32 */
- }
- else {
- /* Yes, it is a proxy request. We've detected the scheme, now
- * we split the URI's components and mark what we've found:
- * - scheme
- * followed by "://", then:
- * - [ username [ ":" password ] "@" ]
- * - hostname
- * [ ":" port ]
- * [ "/" path ... [ "?" query ] ]
- */
-
- /* As per RFC1738:
- * The generic form of a URL is:
- * genericurl = scheme ":" schemepart
- *
- * the scheme is in lower case; interpreters should use case-ignore
- * scheme = 1*[ lowalpha | digit | "+" | "-" | "." ]
- *
- * Extract the scheme:
- */
- s = uri;
- uptr->scheme = getword(p, &s, ':');
- if (uptr->scheme[0] == '\0') {
- uptr->scheme = NULL;
- }
-
- /* URL schemeparts for ip based protocols:
- *
- * ip-schemepart = "//" login [ "/" urlpath ]
- *
- * login = [ user [ ":" password ] "@" ] hostport
- * hostport = host [ ":" port ]
- * host = hostname | hostnumber
- * hostname = *[ domainlabel "." ] toplabel
- * domainlabel = alphadigit | alphadigit *[ alphadigit | "-" ]
alphadigit
- * toplabel = alpha | alpha *[ alphadigit | "-" ] alphadigit
- * alphadigit = alpha | digit
- * hostnumber = digits "." digits "." digits "." digits
- * port = digits
- * user = *[ uchar | ";" | "?" | "&" | "=" ]
- * password = *[ uchar | ";" | "?" | "&" | "=" ]
- * urlpath = *xchar
- */
- /* if IP-schemepart follows, extract host, port etc. */
- if (s[0] == '/' && s[1] == '/') {
- char *tmp;
-
- s += 2;
- if ((tmp = strchr(s, '/')) != NULL) {
- /* In the request_rec structure, the uri is not
- * separated into path & query for proxy requests.
- * But here, we want maximum knowledge about the request,
- * so we still split them. */
- uptr->path = getword_nc(p, &tmp, '?');
- if (uptr->path[0] == '\0') {
- uptr->path = NULL;
- }
-
- if (tmp[0] != '\0') {
- uptr->query = pstrdup(p, tmp);
- }
- }
- else {
- /* the request is just http://hostname - no trailing slash.
- * Provide one:
- */
- uptr->path = "/";
- }
-
- uptr->hostname = getword (p, &s, '/');
- if (uptr->hostname[0] == '\0') {
- uptr->hostname = NULL;
- }
-
- /* disintegrate "[EMAIL PROTECTED]" */
- /* NOTE: using reverse search here because user:password might
- * contain a '@' as well (ftp login: user=ftp : [EMAIL PROTECTED])
- */
- if ((tmp = strrchr(uptr->hostname, '@')) != NULL) {
- uptr->user = uptr->hostname;
- *tmp++ = '\0';
- uptr->hostname = tmp;
-
- /* disintegrate "user:password" */
- if ((tmp = strchr(uptr->user, ':')) != NULL) {
- *tmp++ = '\0';
- uptr->password = tmp;
- }
- }
-
- /* disintegrate "host:port" */
- if ((tmp = strchr(uptr->hostname, ':')) != NULL) {
- *tmp++ = '\0';
- uptr->port_str = tmp;
- uptr->port = (unsigned short) strtol(tmp, &tmp, 10);
- /* Catch possible problem: http://www.apache.org:80@@@/dist/ */
- if (*tmp != '\0')
- ret = HTTP_BAD_REQUEST;
- }
-
- /* Strip any trailing dots in hostname */
- tmp = &uptr->hostname[strlen(uptr->hostname)-1];
- for (; *tmp == '.' && tmp > uptr->hostname; --tmp)
- *tmp = '\0';
-
- /* This name hasn't been looked up yet */
- uptr->dns_looked_up = 0;
- }
- /* If the ip-schemepart doesn't start with "//", deny: */
- else
- ret = HTTP_BAD_REQUEST;
-
- }
-
- return ret;
-}
-#endif
+#ifdef UTIL_URI_REGEX
static regex_t re_uri;
static regex_t re_hostpart;
@@ -382,6 +215,14 @@
int ret;
const char *re_str;
+ memset(uri_delims, 0, sizeof(uri_delims));
+ uri_delims[':'] = T_COLON;
+ uri_delims['/'] = T_SLASH;
+ uri_delims['?'] = T_QUESTION;
+ uri_delims['#'] = T_HASH;
+ uri_delims['@'] = T_AT;
+ uri_delims['\0'] = T_NUL;
+
/* This is a modified version of the regex that appeared in
* draft-fielding-uri-syntax-01. It doesnt allow the uri to contain a
* scheme but no hostinfo or vice versa.
@@ -437,6 +278,7 @@
}
}
+
/* parse_uri_components():
* Parse a given URI, fill in all supplied fields of a uri_components
* structure. This eliminates the necessity of extracting host, port,
@@ -535,24 +377,196 @@
}
}
-#if defined(__EMX__) || defined(WIN32)
- /* Handle path translations for OS/2 and plug security hole.
- * This will prevent "http://www.wherever.com/..\..\/"; from
- * returning a directory for the root drive.
+ if (ret == 0)
+ ret = HTTP_OK;
+ return ret;
+}
+#else
+
+/* Here is the hand-optimized parse_uri_components(). There are some wild
+ * tricks we could pull in assembly language that we don't pull here... like
we
+ * can do word-at-time scans for delimiter characters using the same
technique
+ * that fast memchr()s use. But that would be way non-portable. -djg
+ */
+
+/* We have a table that we can index by character and it tells us if the
+ * character is one of the interesting delimiters. Note that we even get
+ * compares for NUL for free -- it's just another delimiter.
+ */
+
+#define T_COLON 0x01 /* ':' */
+#define T_SLASH 0x02 /* '/' */
+#define T_QUESTION 0x04 /* '?' */
+#define T_HASH 0x08 /* '#' */
+#define T_AT 0x10 /* '@' */
+#define T_NUL 0x80 /* '\0' */
+
+static unsigned char uri_delims[256];
+
+/* it works like this:
+ if (uri_delims[ch] & NOTEND_foobar) {
+ then we're not at a delimiter for foobar
+ }
+*/
+
+/* Note that we optimize the scheme scanning here, we cheat and let the
+ * compiler know that it doesn't have to do the & masking.
+ */
+#define NOTEND_SCHEME (0xff)
+#define NOTEND_HOSTINFO (T_SLASH | T_QUESTION | T_HASH | T_NUL)
+#define NOTEND_PATH (T_QUESTION | T_HASH | T_NUL)
+
+void util_uri_init(void)
+{
+ memset(uri_delims, 0, sizeof(uri_delims));
+ uri_delims[':'] = T_COLON;
+ uri_delims['/'] = T_SLASH;
+ uri_delims['?'] = T_QUESTION;
+ uri_delims['#'] = T_HASH;
+ uri_delims['@'] = T_AT;
+ uri_delims['\0'] = T_NUL;
+}
+
+/* Since we know that the string we're duping is of exactly length l
+ * we don't need to go through the expensive (silly) pstrndup(). We
+ * can do much better on our own. This is worth another 50%
+ * improvement.
+ */
+static char *special_strdup(pool *p, const char *s, size_t l)
+{
+ char *d;
+
+ d = palloc(p, l + 1);
+ memcpy(d, s, l);
+ d[l] = '\0';
+ return d;
+}
+
+/* parse_uri_components():
+ * Parse a given URI, fill in all supplied fields of a uri_components
+ * structure. This eliminates the necessity of extracting host, port,
+ * path, query info repeatedly in the modules.
+ * Side effects:
+ * - fills in fields of uri_components *uptr
+ * - none on any of the r->* fields
+ */
+API_EXPORT(int) parse_uri_components(pool *p, const char *uri,
uri_components *uptr)
+{
+ const char *s;
+ const char *s1;
+ const char *hostinfo;
+ char *endstr;
+ int port;
+
+ /* Initialize the structure. parse_uri() and parse_uri_components()
+ * can be called more than once per request.
*/
- {
- char *s;
+ memset (uptr, '\0', sizeof(*uptr));
+ uptr->is_initialized = 1;
- for (s = uptr->path; (s = strchr(s, '\\')) != NULL; )
- *s = '/';
+ /* We assume the processor has a branch predictor like most --
+ * it assumes forward branches are untaken and backwards are taken.
That's
+ * the reason for the gotos. -djg
+ */
+ if (uri[0] == '/') {
+deal_with_path:
+ /* we expect uri to point to first character of path ... remember
+ * that the path could be empty -- http://foobar?query for example
+ */
+ s = uri;
+ while ((uri_delims[*(unsigned char *)s] & NOTEND_PATH) == 0) {
+ ++s;
+ }
+ if (s != uri) {
+ uptr->path = special_strdup(p, uri, s - uri);
+ }
+ if (*s == 0) {
+ return HTTP_OK;
+ }
+ if (*s == '?') {
+ ++s;
+ s1 = strchr(s, '#');
+ if (s1) {
+ uptr->fragment = pstrdup(p, s1 + 1);
+ uptr->query = special_strdup(p, s, s1 - s);
+ }
+ else {
+ uptr->query = pstrdup(p, s);
+ }
+ return HTTP_OK;
+ }
+ /* otherwise it's a fragment */
+ uptr->fragment = pstrdup(p, s + 1);
+ return HTTP_OK;
}
-#ifndef WIN32 /* for OS/2 only: */
- /* Fix OS/2 HPFS filename case problem. */
- str_tolower(uptr->path);
-#endif
-#endif /* __EMX__ || WIN32 */
- if (ret == 0)
- ret = HTTP_OK;
- return ret;
+ /* find the scheme: */
+ s = uri;
+ while ((uri_delims[*(unsigned char *)s] & NOTEND_SCHEME) == 0) {
+ ++s;
+ }
+ /* scheme must be non-empty and followed by :// */
+ if (s == uri || s[0] != ':' || s[1] != '/' || s[2] != '/') {
+ goto deal_with_path; /* backwards predicted taken! */
+ }
+
+ uptr->scheme = special_strdup(p, uri, s - uri);
+ s += 3;
+ hostinfo = s;
+ while ((uri_delims[*(unsigned char *)s] & NOTEND_HOSTINFO) == 0) {
+ ++s;
+ }
+ uri = s; /* whatever follows hostinfo is start of uri */
+ uptr->hostinfo = special_strdup(p, hostinfo, uri - hostinfo);
+
+ /* If there's a username:[EMAIL PROTECTED]:port, the @ we want is the
last @...
+ * too bad there's no memrchr()... For the C purists, note that hostinfo
+ * is definately not the first character of the original uri so therefore
+ * &hostinfo[-1] < &hostinfo[0] ... and this loop is valid C.
+ */
+ s = uri;
+ do {
+ --s;
+ } while (s >= hostinfo && *s != '@');
+ if (s < hostinfo) {
+ /* again we want the common case to be fall through */
+deal_with_host:
+ /* We expect hostinfo to point to the first character of
+ * the hostname. If there's a port it is the first colon.
+ */
+ s = memchr(hostinfo, ':', uri - hostinfo);
+ if (s == NULL) {
+ /* we expect the common case to have no port */
+ uptr->hostname = special_strdup(p, hostinfo, uri - hostinfo);
+ goto deal_with_path;
+ }
+ uptr->hostname = special_strdup(p, hostinfo, s - hostinfo);
+ ++s;
+ uptr->port_str = special_strdup(p, s, uri - s);
+ if (uri != s) {
+ port = strtol(uptr->port_str, &endstr, 10);
+ uptr->port = port;
+ if (*endstr == '\0' && uptr->port == port) {
+ goto deal_with_path;
+ }
+ /* Invalid characters after ':' found */
+ return HTTP_BAD_REQUEST;
+ }
+ uptr->port = default_port_for_scheme(uptr->scheme);
+ goto deal_with_path;
+ }
+
+ /* first colon delimits username:password */
+ s1 = memchr(hostinfo, ':', s - hostinfo);
+ if (s1) {
+ uptr->user = special_strdup(p, hostinfo, s1 - hostinfo);
+ ++s1;
+ uptr->password = special_strdup(p, s1, s - s1);
+ }
+ else {
+ uptr->user = special_strdup(p, hostinfo, s - hostinfo);
+ }
+ hostinfo = s + 1;
+ goto deal_with_host;
}
+#endif
