Author: joes
Date: Thu Feb 2 13:15:19 2006
New Revision: 374505
URL: http://svn.apache.org/viewcvs?rev=374505&view=rev
Log:
apreq_parse_urlencoded() and apreq_parse_headers() can go quadratic in
CPU because they reset their state on each invocation; they
need to maintain state across invocations in order to remain O(n).
Modified:
httpd/apreq/trunk/CHANGES
httpd/apreq/trunk/STATUS
httpd/apreq/trunk/include/apreq_version.h
httpd/apreq/trunk/library/parser_header.c
httpd/apreq/trunk/library/parser_urlencoded.c
Modified: httpd/apreq/trunk/CHANGES
URL:
http://svn.apache.org/viewcvs/httpd/apreq/trunk/CHANGES?rev=374505&r1=374504&r2=374505&view=diff
==============================================================================
--- httpd/apreq/trunk/CHANGES (original)
+++ httpd/apreq/trunk/CHANGES Thu Feb 2 13:15:19 2006
@@ -4,6 +4,11 @@
@section v2_07 Changes with libapreq2-2.07
+
+- C API [joes]
+ Eliminate potential quadratic behavior in apreq_parse_headers() and
+ apreq_parse_urlencoded().
+
- Perl API [Philip M. Gollucci]
Fix Apache2::Cookie->cookies() to comply with its documentation
Modified: httpd/apreq/trunk/STATUS
URL:
http://svn.apache.org/viewcvs/httpd/apreq/trunk/STATUS?rev=374505&r1=374504&r2=374505&view=diff
==============================================================================
--- httpd/apreq/trunk/STATUS (original)
+++ httpd/apreq/trunk/STATUS Thu Feb 2 13:15:19 2006
@@ -12,9 +12,6 @@
RELEASE SHOWSTOPPERS:
- - The header and url parser go can quadratic in CPU time because
- they fail to maintain their state properly.
-
CURRENT VOTES:
Modified: httpd/apreq/trunk/include/apreq_version.h
URL:
http://svn.apache.org/viewcvs/httpd/apreq/trunk/include/apreq_version.h?rev=374505&r1=374504&r2=374505&view=diff
==============================================================================
--- httpd/apreq/trunk/include/apreq_version.h (original)
+++ httpd/apreq/trunk/include/apreq_version.h Thu Feb 2 13:15:19 2006
@@ -61,7 +61,7 @@
#define APREQ_MINOR_VERSION 5
/** patch level */
-#define APREQ_PATCH_VERSION 6
+#define APREQ_PATCH_VERSION 7
/**
* This symbol is defined for internal, "development" copies of libapreq.
Modified: httpd/apreq/trunk/library/parser_header.c
URL:
http://svn.apache.org/viewcvs/httpd/apreq/trunk/library/parser_header.c?rev=374505&r1=374504&r2=374505&view=diff
==============================================================================
--- httpd/apreq/trunk/library/parser_header.c (original)
+++ httpd/apreq/trunk/library/parser_header.c Thu Feb 2 13:15:19 2006
@@ -30,15 +30,18 @@
struct hdr_ctx {
apr_bucket_brigade *bb;
- enum {
- HDR_NAME,
- HDR_GAP,
- HDR_VALUE,
- HDR_NEWLINE,
- HDR_CONTINUE,
- HDR_COMPLETE,
- HDR_ERROR
- } status;
+ apr_size_t nlen;
+ apr_size_t glen;
+ apr_size_t vlen;
+ enum {
+ HDR_NAME,
+ HDR_GAP,
+ HDR_VALUE,
+ HDR_NEWLINE,
+ HDR_CONTINUE,
+ HDR_COMPLETE,
+ HDR_ERROR
+ } status;
};
/********************* header parsing utils ********************/
@@ -161,23 +164,25 @@
ctx = apr_pcalloc(pool, sizeof *ctx);
ctx->bb = apr_brigade_create(pool, parser->bucket_alloc);
parser->ctx = ctx;
+ ctx->status = HDR_NAME;
}
else
ctx = parser->ctx;
PARSER_STATUS_CHECK(HDR);
+ e = APR_BRIGADE_LAST(ctx->bb);
APR_BRIGADE_CONCAT(ctx->bb, bb);
parse_hdr_brigade:
- ctx->status = HDR_NAME;
/* parse the brigade for CRLF_CRLF-terminated header block,
* each time starting from the front of the brigade.
*/
- for (e = APR_BRIGADE_FIRST(ctx->bb), nlen = glen = vlen = 0;
- e != APR_BRIGADE_SENTINEL(ctx->bb); e = APR_BUCKET_NEXT(e))
+ for (e = APR_BUCKET_NEXT(e);
+ e != APR_BRIGADE_SENTINEL(ctx->bb);
+ e = APR_BUCKET_NEXT(e))
{
apr_size_t off = 0, dlen;
const char *data;
@@ -235,12 +240,12 @@
off = 1;
e = APR_BUCKET_NEXT(e);
}
- ++glen;
+ ++ctx->glen;
ctx->status = HDR_GAP;
goto parse_hdr_bucket;
default:
- ++nlen;
+ ++ctx->nlen;
}
}
@@ -254,7 +259,7 @@
switch (data[off++]) {
case ' ':
case '\t':
- ++glen;
+ ++ctx->glen;
break;
case '\n':
@@ -270,7 +275,7 @@
off = 1;
e = APR_BUCKET_NEXT(e);
}
- ++vlen;
+ ++ctx->vlen;
goto parse_hdr_bucket;
}
}
@@ -280,7 +285,7 @@
case HDR_VALUE:
while (off < dlen) {
- ++vlen;
+ ++ctx->vlen;
if (data[off++] == '\n') {
ctx->status = HDR_NEWLINE;
goto parse_hdr_bucket;
@@ -300,14 +305,14 @@
case '\t':
ctx->status = HDR_CONTINUE;
++off;
- ++vlen;
+ ++ctx->vlen;
break;
default:
/* can parse brigade now */
if (off > 0)
apr_bucket_split(e, off);
- s = split_header_line(¶m, pool, ctx->bb, nlen, glen,
vlen);
+ s = split_header_line(¶m, pool, ctx->bb, ctx->nlen,
ctx->glen, ctx->vlen);
if (parser->hook != NULL && s == APR_SUCCESS)
s = apreq_hook_run(parser->hook, param, NULL);
@@ -317,6 +322,12 @@
}
apreq_value_table_add(¶m->v, t);
+ e = APR_BRIGADE_SENTINEL(ctx->bb);
+ ctx->status = HDR_NAME;
+ ctx->nlen = 0;
+ ctx->vlen = 0;
+ ctx->glen = 0;
+
goto parse_hdr_brigade;
}
@@ -330,7 +341,7 @@
switch (data[off++]) {
case ' ':
case '\t':
- ++vlen;
+ ++ctx->vlen;
break;
case '\n':
@@ -339,7 +350,7 @@
default:
ctx->status = HDR_VALUE;
- ++vlen;
+ ++ctx->vlen;
goto parse_hdr_bucket;
}
}
Modified: httpd/apreq/trunk/library/parser_urlencoded.c
URL:
http://svn.apache.org/viewcvs/httpd/apreq/trunk/library/parser_urlencoded.c?rev=374505&r1=374504&r2=374505&view=diff
==============================================================================
--- httpd/apreq/trunk/library/parser_urlencoded.c (original)
+++ httpd/apreq/trunk/library/parser_urlencoded.c Thu Feb 2 13:15:19 2006
@@ -32,6 +32,8 @@
struct url_ctx {
apr_bucket_brigade *bb;
+ apr_size_t nlen;
+ apr_size_t vlen;
enum {
URL_NAME,
URL_VALUE,
@@ -156,12 +158,11 @@
APREQ_DECLARE_PARSER(apreq_parse_urlencoded)
{
apr_pool_t *pool = parser->pool;
- apr_ssize_t nlen, vlen;
apr_bucket *e;
struct url_ctx *ctx;
if (parser->ctx == NULL) {
- ctx = apr_palloc(pool, sizeof *ctx);
+ ctx = apr_pcalloc(pool, sizeof *ctx);
ctx->bb = apr_brigade_create(pool, parser->bucket_alloc);
parser->ctx = ctx;
ctx->status = URL_NAME;
@@ -170,15 +171,14 @@
ctx = parser->ctx;
PARSER_STATUS_CHECK(URL);
+ e = APR_BRIGADE_LAST(ctx->bb);
APR_BRIGADE_CONCAT(ctx->bb, bb);
parse_url_brigade:
- ctx->status = URL_NAME;
-
- for (e = APR_BRIGADE_FIRST(ctx->bb), nlen = vlen = 0;
- e != APR_BRIGADE_SENTINEL(ctx->bb);
- e = APR_BUCKET_NEXT(e))
+ for (e = APR_BUCKET_NEXT(e);
+ e != APR_BRIGADE_SENTINEL(ctx->bb);
+ e = APR_BUCKET_NEXT(e))
{
apreq_param_t *param;
apr_size_t off = 0, dlen;
@@ -190,7 +190,7 @@
s = APR_SUCCESS;
}
else {
- s = split_urlword(¶m, pool, ctx->bb, nlen, vlen);
+ s = split_urlword(¶m, pool, ctx->bb, ctx->nlen, ctx->vlen);
if (parser->hook != NULL && s == APR_SUCCESS)
s = apreq_hook_run(parser->hook, param, NULL);
@@ -229,7 +229,7 @@
ctx->status = URL_VALUE;
goto parse_url_bucket;
default:
- ++nlen;
+ ++ctx->nlen;
}
}
break;
@@ -241,7 +241,8 @@
case '&':
case ';':
apr_bucket_split(e, off);
- s = split_urlword(¶m, pool, ctx->bb, nlen, vlen);
+ s = split_urlword(¶m, pool, ctx->bb,
+ ctx->nlen, ctx->vlen);
if (parser->hook != NULL && s == APR_SUCCESS)
s = apreq_hook_run(parser->hook, param, NULL);
@@ -251,10 +252,14 @@
}
apreq_value_table_add(¶m->v, t);
+ ctx->status = URL_NAME;
+ ctx->nlen = 0;
+ ctx->vlen = 0;
+ e = APR_BRIGADE_SENTINEL(ctx->bb);
goto parse_url_brigade;
default:
- ++vlen;
+ ++ctx->vlen;
}
}
break;
