apr-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Joe Schaefer <joe+gm...@sunstarsys.com>
Subject Re: [PATCH] table patch using mergesort Re: Frankentables
Date Wed, 18 Jun 2003 00:54:00 GMT
Brian Pane <brian.pane@cnet.com> writes:

> Here's a modification of Joe Schaefer's table patch that uses
> a mergesort to do apr_table_compress and apr_table_overlap.
> 
> This will ensure a worst-case run time of n*log(n) instead
> of n^2.  However, I'm not sure whether the extra complexity
> of the mergesort will hurt the performance on small data
> sets.  Joe, if you have time to test this patch, can you
> let me know how it performs compared to your patch?

Sorry for the delay, Brian.  After 3 passes of

  % ab -H "Accept-Language: en" -H "Accept-Encoding: gzip" \
  -H "Accept-Charset: *" -H "Referer: http://localhost/"   \
  -H "Cookie: foo=bar" -n 50000 -c 50 http://127.0.0.1:8080/foo

I ran

  % op_time -rl /home/joe/apache2/bin/httpd | perl -nal             \
  -e 'if (/table|overlap/) { $ops += $F[1]; $pct += $F[2]; print }' \
  -e 'END { printf "\nTOTAL:\t %d \t  %.6f %%\n", $ops, $pct }'

Results:
--------------------------------------------------
CVS HEAD

0000c16c 521      1.16334     apr_table_get           ...
0000d0dc 285      0.636374    apr_table_overlap       ...
0000c47c 260      0.580552    apr_table_setn          ...
0000bff0 260      0.580552    apr_table_make          ...
0000cea0 229      0.511332    overlap_hash            ...
0000cb5c 190      0.424249    apr_table_addn          ...
0000c968 149      0.332701    apr_table_mergen        ...
0000c0e4 130      0.290276    table_reindex           ...
0000bfd4 84       0.187563    apr_is_empty_table      ...
0000bfcc 82       0.183097    apr_table_elts          ...
0000cc70 76       0.1697      apr_table_vdo           ...
0000cc48 57       0.127275    apr_table_do            ...
0000c684 41       0.0915485   apr_table_unset         ...

TOTAL:	 2364 	  5.278559 %

--------------------------------------------------
JOE'S-PATCH

0000c5fc 524      1.16865     apr_table_get           ...
0000c908 325      0.724832    apr_table_setn          ...
0000c3bc 290      0.646773    apr_table_compress      ...
0000d344 210      0.468353    apr_table_addn          ...
0000c134 177      0.394754    apr_table_make          ...
0000cfa8 131      0.292163    apr_table_mergen        ...
0000d5b8 101      0.225255    apr_table_vdo           ...
0000c0ec 76       0.169499    apr_is_empty_table      ...
0000c0e4 66       0.147197    apr_table_elts          ...
0000d590 56       0.124894    apr_table_do            ...
0000cb10 51       0.113743    apr_table_unset         ...

TOTAL:	 2007 	  4.476113 %

--------------------------------------------------
BRIAN'S-PATCH

0000c1e8 559      1.24604     apr_table_get           ...
0000c4f8 253      0.563952    apr_table_setn          ...
0000ce94 203      0.452499    table_mergesort         ...
0000c06c 187      0.416834    apr_table_make          ...
0000cbd8 179      0.399001    apr_table_addn          ...
0000d048 138      0.30761     apr_table_compress      ...
0000ccec 86       0.191699    apr_table_vdo           ...
0000c9e4 84       0.187241    apr_table_mergen        ...
0000c160 82       0.182783    table_reindex           ...
0000c048 71       0.158263    apr_table_elts          ...
0000c050 62       0.138202    apr_is_empty_table      ...
0000ccc4 57       0.127056    apr_table_do            ...
0000c700 54       0.120369    apr_table_unset         ...

TOTAL:	 2015 	  4.491549 %


Looks like the two patches are virtually identical overall, and your 
mergesort patch handles the worst case scenario as well as current cvs 
does.

Reagarding the worst-case scenario: both apache-1.3 and httpd-2
allow 100 8KB header lines, and neither one runs any sanity checks on the 
header's name length.  Conceivably each of the 100 header names could 
be 8KB long, perhaps differing only in the last character.  AFAICT, the 
simplest way to reduce the effectiveness of a potential DoS attack on the 
merging algorithm would be to add a length check to httpd-2/protocol.c 
around line 780:

  if (!(value = strchr(last_field, ':')) /* Find ':' within */
        || value - last_field > 100 ) {  /* first 100 chars or */
      r->status = HTTP_BAD_REQUEST       /* abort bad request */

-- 
Joe Schaefer


Mime
View raw message