Brian Pane <[EMAIL PROTECTED]> 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
