PoC folded into trunk… Let's go ;) On Aug 25, 2011, at 8:16 AM, Plüm, Rüdiger, VF-Group wrote:
> > >> -----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 >