httpd-apreq-cvs mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From j...@apache.org
Subject svn commit: r374505 - in /httpd/apreq/trunk: CHANGES STATUS include/apreq_version.h library/parser_header.c library/parser_urlencoded.c
Date Thu, 02 Feb 2006 21:15:22 GMT
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(&param, pool, ctx->bb, nlen, glen, vlen);
+                    s = split_header_line(&param, 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(&param->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(&param, pool, ctx->bb, nlen, vlen);
+                s = split_urlword(&param, 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(&param, pool, ctx->bb, nlen, vlen);
+                    s = split_urlword(&param, 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(&param->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;



Mime
View raw message