On Fri, 30 Mar 2001, Bill Stoddard wrote:
> There are still a lot of cycles lying around to pick up, like the call to
> qsort in apr_table_overlap that occurs in get_mime_headers(), a jillion
> strlen() calls to get the length of the same string multiple times, etc.
watch out -- that qsort() is there as part of a fix for an O(n^2) DoS
attack. there's two O(n^2) behaviours which are avoided by
ap_table_overlap. one is the quadratic memory consumption of
concatenating a bunch of smaller strings one at a time; and the other is a
quadratic number of header comparisons.
i think the worst case scenario for the pre-overlap code was header input
something like this:
a: a
b: b
a: a
b: b
...
-dean
