> -----Original Message----- > From: Stefan Fritsch > Sent: Donnerstag, 25. August 2011 01:39 > To: dev@httpd.apache.org > Subject: Re: Fixing Ranges > > On Thursday 25 August 2011, Greg Ames wrote: > > On Wed, Aug 24, 2011 at 5:16 PM, Stefan Fritsch <s...@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). >
I guess the following should be adjusted with this patch: 1. Do the same integer casting thing apr_brigade_partition does. So convert everything to apr_uint64_t and work with this. 2. Doing a read on a bucket can change its length. So we need to check afterwards if we still can split the bucket and if not might do a read on the next bucket until we are fine. 3. We should do the read bucket thing for the last bucket as well. I think it would be best if you could commit this PoC patch as is (or with adjustments according to the comments above) to trunk and we polish it up in trunk until it is fine. Regards Rüdiger
