Mailing-List: contact dev-help@httpd.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@httpd.apache.org
Received-SPF: pass (nike.apache.org: local policy)
Content-class: urn:content-classes:message
MIME-Version: 1.0
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
Subject: RE: Fixing Ranges
Date: Thu, 25 Aug 2011 14:16:50 +0200
Message-ID: 
 <E563FB5AB3F02844AC749BA39E494AB4052FC0FE@VF-MBX11.internal.vodafone.com>
In-Reply-To: <201108250138.49474.sf@sfritsch.de>
Thread-Topic: Fixing Ranges
Thread-Index: Acxitw4n2FAlxlGfTd20XwzdHH3lRQAaQkyw
References: <20110824220643.17819937@baldur>
 <201108242316.18134.sf@sfritsch.de>
 <CAHSOX_Bm+uJ6bZ4tATa_1kmHGZizA_5tcVMt=-WgY2ddi5WyXw@mail.gmail.com>
 <201108250138.49474.sf@sfritsch.de>
From: =?iso-8859-1?Q?=22Pl=FCm=2C_R=FCdiger=2C_VF-Group=22?=
 <ruediger.pluem@vodafone.com>
To: <dev@httpd.apache.org>

=20

> -----Original Message-----
> From: Stefan Fritsch =20
> Sent: Donnerstag, 25. August 2011 01:39
> To: dev@httpd.apache.org
> Subject: Re: Fixing Ranges
>=20
> On Thursday 25 August 2011, Greg Ames wrote:
> > On Wed, Aug 24, 2011 at 5:16 PM, Stefan Fritsch <sf@sfritsch.de>=20
> 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?
> >=20
> > How does apr_brigade_partition contribute to quadratic growth?=20
> > Does the original brigade end up with a lot of one byte buckets?
>=20
> Yes, it splits the buckets in the original brigade, creating=20
> up to two=20
> new buckets for every range. These split one-byte buckets are then=20
> copied again for each of the subsequent ranges.
>=20
> The attached PoC patch does not change the original brigade and seems=20
> to fix the DoS for me. It needs some more work and some review for=20
> integer overflows, though. (apr_brigade_partition does some=20
> interesting things there).
>=20

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=FCdiger