httpd-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Stefan Fritsch ...@sfritsch.de>
Subject Re: Fixing Ranges
Date Wed, 24 Aug 2011 23:38:49 GMT
On Thursday 25 August 2011, Greg Ames wrote:
> On Wed, Aug 24, 2011 at 5:16 PM, Stefan Fritsch <sf@sfritsch.de> 
wrote:
> > I have another idea: Instead of using apr_brigade_partition write
> > a new function ap_brigade_copy_part that leaves the original
> > brigade untouched. It would copy the necessary buckets to a new
> > brigade and then split the first and last of those copied
> > buckets as necessary and destroy the excess buckets. AFAICS,
> > this would reduce the quadratic growth into linear. Do you think
> > that would solve our problems?
> 
> How does apr_brigade_partition contribute to quadratic growth? 
> Does the original brigade end up with a lot of one byte buckets?

Yes, it splits the buckets in the original brigade, creating up to two 
new buckets for every range. These split one-byte buckets are then 
copied again for each of the subsequent ranges.

The attached PoC patch does not change the original brigade and seems 
to fix the DoS for me. It needs some more work and some review for 
integer overflows, though. (apr_brigade_partition does some 
interesting things there).

Mime
View raw message