[PATCH] Avoid unnecessary brigade splits on core input and output filters. WAS: EOS or FLUSH buckets

[Juan Rivera <Ju...@citrix.com>]

I'm seen this problem with a SOCKS protocol module I wrote.

I'm including a patch that fixes this problem. It does what I mentioned
below. In the input filter, it moves the buckets rather than creating a new
brigade and then concatenate. In the output filter it splits the brigade
after a flush bucket only if there are buckets after the flush.

Juan

-----Original Message-----
From: gregames@apache.org [mailto:gregames@apache.org] 
Sent: Tuesday, June 10, 2003 3:41 PM
To: dev@httpd.apache.org
Subject: Re: EOS or FLUSH buckets

Juan Rivera wrote:

> Right, my module leaks memory because the core input and output filters 
> split the bucket brigades. So it keeps creating more and more bucket 
> brigades that are not released until the connection is gone.

When you see this, are we talking about a lot of HTTP requests pipelined on
a 
single connection, or a single HTTP request that lasts a long time?

> First of all, I think the split in the core input filter (READBYTES) 
> should be optimized because all it is doing is splitting the brigade to 
> concatenate it into another brigade. Wouldn't be more efficient to do a 
> "move buckets from brigade ctx->b to b" and avoid creating a temporary 
> brigade?
> 
> So for the output side, when I send a flush, it splits the brigade. If 
> the flush is the last bucket, this might not be necessary, what do you 
> think?

I'll defer these two questions to our Bucketmeister and/or efficiency
experts. 
(Cliff? Brian?)

> On the topic of EOS, I think that if the last bucket is an EOS and is 
> not a keep alive connection it should not hold the data but it currently 
> does.

Maybe.  But if it's not a keepalive connection, we should be sending a FLUSH

bucket within microseconds, no?  OK, maybe that path could be optimized.
But 
we'd have to be careful because keepalive connections are very common.  We 
wouldn't want to penalize the hot path by optimizing for the less common
case.

Greg

Re: [PATCH] Avoid unnecessary brigade splits on core input and output filters. WAS: EOS or FLUSH buckets

[gr...@apache.org]

gregames@apache.org wrote:
> Juan Rivera wrote:
> 
>> I'm seen this problem with a SOCKS protocol module I wrote.
>>
>> I'm including a patch that fixes this problem. It does what I 
>> mentioned below. In the input filter, it moves the buckets rather than 
>> creating a new brigade and then concatenate. In the output filter it 
>> splits the brigade after a flush bucket only if there are buckets 
>> after the flush.
> 
> 
> +1 to the piece that affects core_output_filter.  
> 
> I'll test and commit that part of it.

done.  Thanks again, Juan.

Greg

Re: [PATCH] Avoid unnecessary brigade splits on core input and output filters. WAS: EOS or FLUSH buckets

[gr...@apache.org]

Juan Rivera wrote:
> I'm seen this problem with a SOCKS protocol module I wrote.
> 
> I'm including a patch that fixes this problem. It does what I mentioned 
> below. In the input filter, it moves the buckets rather than creating a 
> new brigade and then concatenate. In the output filter it splits the 
> brigade after a flush bucket only if there are buckets after the flush.

+1 to the piece that affects core_output_filter.  A small patch is often worth a 
thousand words.

I remember seeing that code do unneccessary splits when I was working on a fd 
leak on keepalive connections with multiple requests.  The empty brigades caused 
my new code to blow up for a while, so I considered it a good test case at the 
time.  But I agree, it shouldn't split off empty brigades when they are so easy 
to avoid.

I'll test and commit that part of it.  Keep up the good work!

Greg

Re: [PATCH] Avoid unnecessary brigade splits on core input and output filters. WAS: EOS or FLUSH buckets

[Cliff Woolley <jw...@virginia.edu>]

On Thu, 12 Jun 2003, Justin Erenkrantz wrote:

> I suggest that this be created as a macro called
> APR_BRIGADE_CONCAT_UNTIL() as I don't think understanding apr_ring.h
> should be a pre-req for writing filters.  ;-)   -- justin

I'm fine with that... I'll try to find some time tonight to add it to
apr_ring.h and apr_brigade.h and test it.

--Cliff

Re: [PATCH] Avoid unnecessary brigade splits on core input and output filters. WAS: EOS or FLUSH buckets

[Cliff Woolley <jw...@virginia.edu>]

On Thu, 12 Jun 2003, Justin Erenkrantz wrote:

> What would happen if e weren't there and it were passed to
> APR_RING_SPLIT_TAIL?  -- justin

By "weren't there," I assume you mean "were in some other brigade".

Then the supposed sequence of buckets represented by
APR_BRIGADE_FIRST(ctx->b)...APR_BUCKET_PREV(e) would be broken, since if
bucket e is not in ctx->b then neither is APR_BUCKET_PREV(e).  Inserting
this into brigade b would cause b to be a broken ring, and the fixup code
would end up halfway inserting e into ctx->b.

In other words, it would be bad.  :)

--Cliff

Re: [PATCH] Avoid unnecessary brigade splits on core input and output filters. WAS: EOS or FLUSH buckets

[Justin Erenkrantz <ju...@erenkrantz.com>]

On Thu, Jun 12, 2003 at 05:55:10PM -0400, Cliff Woolley wrote:
> I should point out that the above code does one thing that my code does
> not: it allows for bucket e to be completely absent from ctx->b.  (In
> which case ctx->b would be left completely empty at the end of the loop.)
> My code assumes that e is guaranteed to be somewhere in brigade ctx->b.
> (In which case ctx->b will have at least one bucket (e) left in it at the
> end of the loop.)

What would happen if e weren't there and it were passed to
APR_RING_SPLIT_TAIL?  -- justin

Re: [PATCH] Avoid unnecessary brigade splits on core input and output filters. WAS: EOS or FLUSH buckets

[Cliff Woolley <jw...@virginia.edu>]

> > On Thu, 12 Jun 2003, Justin Erenkrantz wrote:
> >
> > > for (bucket = APR_BUCKET_FIRST(ctx->b);
> > >      bucket != e && bucket != APR_BRIGADE_LAST(ctx->b);
> > >      bucket = APR_BUCKET_NEXT(bucket)) {
> > >    apr_bucket_remove(bucket);
> > >    APR_BRIGADE_INSERT_TAIL(b, bucket);
> > > }


PS: if you *were* going to write it this way, then it would actually be:

for (bucket = APR_BRIGADE_FIRST(ctx->b);
     bucket != e && bucket != APR_BRIGADE_SENTINEL(ctx->b);
     bucket = APR_BRIGADE_FIRST(ctx->b))
{
    apr_bucket_remove(bucket);
    APR_BRIGADE_INSERT_TAIL(b, bucket);
}

The second line has to test against the sentinel, not APR_BRIGADE_LAST(),
because otherwise the last bucket in the brigade could never be copied.
The third line has to always use APR_BRIGADE_FIRST(), because after an
iteration of the loop, APR_BUCKET_NEXT(bucket) now points to
APR_BRIGADE_SENTINEL(b) [since bucket is now the last bucket in b], not to
the bucket you really want, which is the one that's now the first bucket
in ctx->b.

I should point out that the above code does one thing that my code does
not: it allows for bucket e to be completely absent from ctx->b.  (In
which case ctx->b would be left completely empty at the end of the loop.)
My code assumes that e is guaranteed to be somewhere in brigade ctx->b.
(In which case ctx->b will have at least one bucket (e) left in it at the
end of the loop.)

--Cliff

Re: [PATCH] Avoid unnecessary brigade splits on core input and output filters. WAS: EOS or FLUSH buckets

[Justin Erenkrantz <ju...@erenkrantz.com>]

On Thu, Jun 12, 2003 at 05:07:32PM -0400, Cliff Woolley wrote:
> On Thu, 12 Jun 2003, Justin Erenkrantz wrote:
> 
> > for (bucket = APR_BUCKET_FIRST(ctx->b);
> >      bucket != e && bucket != APR_BRIGADE_LAST(ctx->b);
> >      bucket = APR_BUCKET_NEXT(bucket)) {
> >    apr_bucket_remove(bucket);
> >    APR_BRIGADE_INSERT_TAIL(b, bucket);
> > }
> 
> No!  Bad!!  The whole beauty of the ring data structure is that all of
> these operations can be done in constant time, no loops.  Bear with me,
> and I'll explain.

Heh.  I didn't say it was optimal, but that's the code I'd write.  But,
if APR_RING_SPLICE_TAIL can produce equivalent results, then great.

> if (APR_BRIGADE_FIRST(ctx->b) != e)
> {
>     /* move the sequence into the new brigade */
>     APR_RING_SPLICE_TAIL(&b->list,
>                          APR_BRIGADE_FIRST(ctx->b),
>                          APR_BUCKET_PREV(e),
>                          apr_bucket, link);
> 
>     /* fixup the dangling pointers in ctx->b */
>     APR_BRIGADE_FIRST(ctx->b) = e;
>     APR_BUCKET_PREV(e) = APR_BRIGADE_SENTINEL(ctx->b);
> }

I suggest that this be created as a macro called
APR_BRIGADE_CONCAT_UNTIL() as I don't think understanding apr_ring.h
should be a pre-req for writing filters.  ;-)   -- justin

Re: [PATCH] Avoid unnecessary brigade splits on core input and output filters. WAS: EOS or FLUSH buckets

[Cliff Woolley <jw...@virginia.edu>]

On Thu, 12 Jun 2003, Justin Erenkrantz wrote:

> for (bucket = APR_BUCKET_FIRST(ctx->b);
>      bucket != e && bucket != APR_BRIGADE_LAST(ctx->b);
>      bucket = APR_BUCKET_NEXT(bucket)) {
>    apr_bucket_remove(bucket);
>    APR_BRIGADE_INSERT_TAIL(b, bucket);
> }

No!  Bad!!  The whole beauty of the ring data structure is that all of
these operations can be done in constant time, no loops.  Bear with me,
and I'll explain.


> If you understand the type safety checks it is attempting, you are a far
> more intelligent person than I.  =)

Well, I dunno about that... I do understand them but then again I've
focused on them since literally the day I started contributing to this lil
ole web server.


The following code assumes that ctx->b has at least one bucket in it,
namely e.


if (APR_BRIGADE_FIRST(ctx->b) != e)
{
    /* move the sequence into the new brigade */
    APR_RING_SPLICE_TAIL(&b->list,
                         APR_BRIGADE_FIRST(ctx->b),
                         APR_BUCKET_PREV(e),
                         apr_bucket, link);

    /* fixup the dangling pointers in ctx->b */
    APR_BRIGADE_FIRST(ctx->b) = e;
    APR_BUCKET_PREV(e) = APR_BRIGADE_SENTINEL(ctx->b);
}

Lovely, eh?  I didn't actually test this to make sure it's 100% right, but
conceptually I believe it should do the trick.

--Cliff

Re: [PATCH] Avoid unnecessary brigade splits on core input and output filters. WAS: EOS or FLUSH buckets

[Justin Erenkrantz <ju...@erenkrantz.com>]

--On Wednesday, June 11, 2003 5:14 PM -0400 Cliff Woolley 
<jw...@virginia.edu> wrote:

> On Tue, 10 Jun 2003, Justin Erenkrantz wrote:
>
>> What you are really wanting to do is a partial concatenation of the brigade.
>> Something like (not there, but it could be easily added):
>>
>> APR_BRIGADE_CONCAT_UNTIL(b, ctx->b, e)
>
> I'm not sure I see exactly where you're going, but you might be able to
> get what you want by doing an APR_RING_SPLICE().

Perhaps.  My thought is that all of ctx->b up to e should be inserted into b.

for (bucket = APR_BUCKET_FIRST(ctx->b);
     bucket != e && bucket != APR_BRIGADE_LAST(ctx->b);
     bucket = APR_BUCKET_NEXT(bucket)) {
   apr_bucket_remove(bucket);
   APR_BRIGADE_INSERT_TAIL(b, bucket);
}

Um, something like that.  It's 1AM and that's about all the pseudocode I can 
write.

If APR_RING_SPLICE can do it, yea.  But, I've found apr_ring.h to be a 
complete black hole.  If you understand the type safety checks it is 
attempting, you are a far more intelligent person than I.  =)  -- justin

Re: [PATCH] Avoid unnecessary brigade splits on core input and output filters. WAS: EOS or FLUSH buckets

[Cliff Woolley <jw...@virginia.edu>]

On Tue, 10 Jun 2003, Justin Erenkrantz wrote:

> What you are really wanting to do is a partial concatenation of the brigade.
> Something like (not there, but it could be easily added):
>
> APR_BRIGADE_CONCAT_UNTIL(b, ctx->b, e)

I'm not sure I see exactly where you're going, but you might be able to
get what you want by doing an APR_RING_SPLICE().

--Cliff

Re: [PATCH] Avoid unnecessary brigade splits on core input and output filters. WAS: EOS or FLUSH buckets

[Justin Erenkrantz <ju...@erenkrantz.com>]

--On Tuesday, June 10, 2003 4:59 PM -0400 Juan Rivera <Ju...@citrix.com> 
wrote:

> I'm including a patch that fixes this problem. It does what I mentioned
> below. In the input filter, it moves the buckets rather than creating a new
> brigade and then concatenate. In the output filter it splits the brigade
> after a flush bucket only if there are buckets after the flush.

What you are really wanting to do is a partial concatenation of the brigade. 
Something like (not there, but it could be easily added):

APR_BRIGADE_CONCAT_UNTIL(b, ctx->b, e)

The difference between APR_BRIGADE_CONCAT_UNTIL and APR_BRIGADE_CONCAT would 
be that ctx->b may still have content if e is encountered.  APR_BRIGADE_CONCAT 
(and APR_RING_CONCAT) are O(1), but this'd be O(n), but that's okay as it'd 
save the space of the new brigade in comparison to 
apr_brigade_split/apr_brigade_concat, I guess.

You should reconstruct the AP_MODE_SPECULATIVE case to do a partial for loop 
rather than apr_brigade_split, etc.  An APR_BRIGADE_CONCAT_UNTIL isn't enough 
as you want to copy the buckets, but a simple for-loop should do.

Skip the APR_BRIGADE_CONCAT at the end as newbb should be empty if you follow 
the above strategies.

I think the output FLUSH part looks okay.

I'd also suggest reading over our style guide.  Please watch your indention, 
C++-style comments, and tabs.  It makes your patch almost impossible to 
review.  Since it's attached with application/octet-stream I can't review it 
inline either.

Back to my mad-paper-writing cave... -- justin