[SPDY] Refactor SpdySession's write queue

[SPDY] Refactor SpdySession's write queue

This is in preparation for replacing the various IOBuffers used for reads/writes
with a single SpdyBuffer class.

Replace the priority queue of SpdyIOBufferProducers with a SpdyWriteQueue object,
which is an an array of FIFO queues binned by priority.
The priority queue was looking only at priority and so was not guaranteeing
FIFO behavior among producers with the same priority.

Remove the frame queue in SpdyStream and instead have it use the session's
write queue directly.

Remove unused fields from SpdyIOBuffer and clean it up.

Propagate and handle errors from SpdyCredentialBuilder::Build.

Rename SpdyIOBufferProducer to SpdyFrameProducer, have it return a SpdyFrame,
clean up its interface, and move the stream-activating logic out of it.

Replace uses of std::list with std::deque.

Steamline logic in SpdySession that deals with the write queue.

Convert some raw pointers to scoped_ptr<>.

Convert a use of Unretained() in SpdySession to use the weak pointer factory.

BUG=176582
Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=192975

Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=194102

[akalin, 2013-03-24 07:07:48]

+rch for review

[Ryan Hamilton, 2013-03-24 15:22:54]

https://codereview.chromium.org/13009012/diff/1/net/spdy/spdy_session.h
File net/spdy/spdy_session.h (right):

https://codereview.chromium.org/13009012/diff/1/net/spdy/spdy_session.h#newco...
net/spdy/spdy_session.h:172: virtual SpdyStream* GetStream() = 0;
See this comment on the CL which landed SpdyIOBufferProducer:

https://chromiumcodereview.appspot.com/10448083/diff/22001/net/spdy/spdy_sess...

I had such a method in my initial implementation, but willchan requested it be
removed.  Can you refactor accordingly?

[akalin, 2013-03-24 18:24:13]

+willchan re. question

https://codereview.chromium.org/13009012/diff/1/net/spdy/spdy_session.h
File net/spdy/spdy_session.h (right):

https://codereview.chromium.org/13009012/diff/1/net/spdy/spdy_session.h#newco...
net/spdy/spdy_session.h:172: virtual SpdyStream* GetStream() = 0;
On 2013/03/24 15:22:54, Ryan Hamilton wrote:
> See this comment on the CL which landed SpdyIOBufferProducer:
> 
>
https://chromiumcodereview.appspot.com/10448083/diff/22001/net/spdy/spdy_sess...
> 
> I had such a method in my initial implementation, but willchan requested it be
> removed.  Can you refactor accordingly?

Hmm I looked at the comment but willchan didn't state his reason.

I think it's simpler to have this method, as it avoids the need for the extra
map and lets us move the activate-if-necessary logic back to the SpdySession.

willchan, can you elaborate on why you don't like this method?

[willchan no longer on Chromium, 2013-03-24 18:58:22]

https://codereview.chromium.org/13009012/diff/1/net/spdy/spdy_session.h
File net/spdy/spdy_session.h (right):

https://codereview.chromium.org/13009012/diff/1/net/spdy/spdy_session.h#newco...
net/spdy/spdy_session.h:172: virtual SpdyStream* GetStream() = 0;
On 2013/03/24 18:24:14, akalin wrote:
> On 2013/03/24 15:22:54, Ryan Hamilton wrote:
> > See this comment on the CL which landed SpdyIOBufferProducer:
> > 
> >
>
https://chromiumcodereview.appspot.com/10448083/diff/22001/net/spdy/spdy_sess...
> > 
> > I had such a method in my initial implementation, but willchan requested it
be
> > removed.  Can you refactor accordingly?
> 
> Hmm I looked at the comment but willchan didn't state his reason.
> 
> I think it's simpler to have this method, as it avoids the need for the extra
> map and lets us move the activate-if-necessary logic back to the SpdySession.
> 
> willchan, can you elaborate on why you don't like this method?

Layering. This is at the frame level, which is lower level than streams. It
feels like a minor layering violation (kind of like RTTI), especially since not
all frames have streams. A HasStream() or GetStreamId() wouldn be less of a
violation that exposing a raw SpdyStream*.

Now, layers are obviously arbitrary. Oftentimes tighter coupling and removal of
abstraction layers can simplify code. There are tradeoffs here. I generally err
on the side of maintaining abstraction boundaries throughout most of my code
unless it's obviously too cumbersome and would be much simpler to eliminate the
arbitrary mental layer.

I leave that up to you guys.

[akalin, 2013-03-24 19:16:08]

On 2013/03/24 18:58:22, willchan wrote:
> Layering. This is at the frame level, which is lower level than streams. It
> feels like a minor layering violation (kind of like RTTI), especially since
not
> all frames have streams. A HasStream() or GetStreamId() wouldn be less of a
> violation that exposing a raw SpdyStream*.
> 
> Now, layers are obviously arbitrary. Oftentimes tighter coupling and removal
of
> abstraction layers can simplify code. There are tradeoffs here. I generally
err
> on the side of maintaining abstraction boundaries throughout most of my code
> unless it's obviously too cumbersome and would be much simpler to eliminate
the
> arbitrary mental layer.
> 
> I leave that up to you guys.

Okay.

What do you think about removing GetStream() from the interface, but then making
the write queue(s) hold a struct { SpdyStream*; SpdyFrameProducer* }? (It gets
the SpdyStream when the stream itself calls SetStreamHasWriteAvailable() on the
session.)

[akalin, 2013-03-24 19:36:35]

On 2013/03/24 19:16:08, akalin wrote:
> Okay.
> 
> What do you think about removing GetStream() from the interface, but then
making
> the write queue(s) hold a struct { SpdyStream*; SpdyFrameProducer* }? (It gets
> the SpdyStream when the stream itself calls SetStreamHasWriteAvailable() on
the
> session.)

(I'll proceed with this unless I hear otherwise.)

[Ryan Hamilton, 2013-03-25 17:09:05]

On 2013/03/24 19:36:35, akalin wrote:
> On 2013/03/24 19:16:08, akalin wrote:
> > Okay.
> > 
> > What do you think about removing GetStream() from the interface, but then
> making
> > the write queue(s) hold a struct { SpdyStream*; SpdyFrameProducer* }? (It
gets
> > the SpdyStream when the stream itself calls SetStreamHasWriteAvailable() on
> the
> > session.)
> 
> (I'll proceed with this unless I hear otherwise.)

SGTM

[akalin, 2013-03-26 03:05:28]

Made the write queue store a SpdyStream/SpdyFrameProducer pair. Also moved all
the write queue logic into its own file and added tests.

Also, got rid of the frame queue in SpdyStream.

There's room for more refactoring, but this is good for now.

PTAL!

[akalin, 2013-03-26 04:32:33]

(I don't know why the trybots aren't working, even if I specify -r.  Sigh.)

[akalin, 2013-03-27 23:43:16]

ping!

[Ryan Hamilton, 2013-03-28 15:51:04]

Looks great.  Just a number of nits...

https://codereview.chromium.org/13009012/diff/30001/net/spdy/spdy_session.cc
File net/spdy/spdy_session.cc (right):

https://codereview.chromium.org/13009012/diff/30001/net/spdy/spdy_session.cc#...
net/spdy/spdy_session.cc:679: DCHECK_NE(rv, ERR_IO_PENDING);
if you want to save a line, you could write this as:
DCHECK_NE(ERR_IO_PENDING, rv);
if (rv != OK) 
  return rv;

Not remotely sure if that's better :>

https://codereview.chromium.org/13009012/diff/30001/net/spdy/spdy_session.cc#...
net/spdy/spdy_session.cc:721: SpdyStreamId stream_id,
I think you can move this to the previous line, and line up all the args
accordingly, right?  (Hard to tell without an editor, so I could well be wrong)

https://codereview.chromium.org/13009012/diff/30001/net/spdy/spdy_session.cc#...
net/spdy/spdy_session.cc:983: // size.
I wonder if the caller actually cares about the number of bytes written?  When
you clean up OnWriteComplete, I wonder if you can nuke this whole calculation.

https://codereview.chromium.org/13009012/diff/30001/net/spdy/spdy_write_queue.cc
File net/spdy/spdy_write_queue.cc (right):

https://codereview.chromium.org/13009012/diff/30001/net/spdy/spdy_write_queue...
net/spdy/spdy_write_queue.cc:48: DCHECK_EQ(stream->priority(), priority);
alternatively, you could have two Enqueue methods, one which takes a stream, and
one which takes a priority.  *shrug*  Might be cleaner, might be more code.

https://codereview.chromium.org/13009012/diff/30001/net/spdy/spdy_write_queue...
net/spdy/spdy_write_queue.cc:56: if (!queue_[i].empty()) {
nit: I think I would write this as:
if (queue_[i].empty())
  continue;

early "return" ftw which lets you out-dent the rest of the block.

https://codereview.chromium.org/13009012/diff/30001/net/spdy/spdy_write_queue...
net/spdy/spdy_write_queue.cc:91: queue_[stream->priority()].push_back(*it);
It looks like deque support an erase() method which returns an iterator to the
next element after the erased element.  I think that might be better than
reconstructing the deque.

Out of curiosity, would an std::list work as well as a deque here?

https://codereview.chromium.org/13009012/diff/30001/net/spdy/spdy_write_queue.h
File net/spdy/spdy_write_queue.h (right):

https://codereview.chromium.org/13009012/diff/30001/net/spdy/spdy_write_queue...
net/spdy/spdy_write_queue.h:55: class NET_EXPORT_PRIVATE SpdyWriteQueue {
Since this WriteQueue is only used by the Session, I think I would split the
producer definitions out into spdy_frame_producer.h which spdy_stream would
include, leaving only the producer in this file which would be included by
spdy_session.

https://codereview.chromium.org/13009012/diff/30001/net/spdy/spdy_write_queue...
net/spdy/spdy_write_queue.h:62: // producer is associated with the session.
nit: if the frame is *not* associated with *a stream*.

I think?

https://codereview.chromium.org/13009012/diff/30001/net/spdy/spdy_write_queue...
net/spdy/spdy_write_queue.h:65: const scoped_refptr<SpdyStream>& stream);
out of curiosity, why is this a const scoped_refptr& and not a scoped_refptr?

https://codereview.chromium.org/13009012/diff/30001/net/spdy/spdy_write_queue...
net/spdy/spdy_write_queue.h:67: // Dequeues the next frame producer and its
associated
nit: Can you comment on the ordering guarantees of Dequeue.  In particular the
fifo behavior within a priority, and priority order amongst priorities.  You
mention the ordering at the class comment, but it think it would be helpful to
mention here, since the ordering really comes into play here.

[akalin, 2013-04-06 01:17:48]

PTAL!

https://codereview.chromium.org/13009012/diff/30001/net/spdy/spdy_session.cc
File net/spdy/spdy_session.cc (right):

https://codereview.chromium.org/13009012/diff/30001/net/spdy/spdy_session.cc#...
net/spdy/spdy_session.cc:679: DCHECK_NE(rv, ERR_IO_PENDING);
On 2013/03/28 15:51:04, Ryan Hamilton wrote:
> if you want to save a line, you could write this as:
> DCHECK_NE(ERR_IO_PENDING, rv);
> if (rv != OK) 
>   return rv;
> 
> Not remotely sure if that's better :>

Done.

https://codereview.chromium.org/13009012/diff/30001/net/spdy/spdy_session.cc#...
net/spdy/spdy_session.cc:721: SpdyStreamId stream_id,
On 2013/03/28 15:51:04, Ryan Hamilton wrote:
> I think you can move this to the previous line, and line up all the args
> accordingly, right?  (Hard to tell without an editor, so I could well be
wrong)

Done.

https://codereview.chromium.org/13009012/diff/30001/net/spdy/spdy_session.cc#...
net/spdy/spdy_session.cc:983: // size.
On 2013/03/28 15:51:04, Ryan Hamilton wrote:
> I wonder if the caller actually cares about the number of bytes written?  When
> you clean up OnWriteComplete, I wonder if you can nuke this whole calculation.

Yeah, the callers do care about the number of bytes written because of partial
writes; only SpdyHttpStream doesn't care since it doesn't send anything.

https://codereview.chromium.org/13009012/diff/30001/net/spdy/spdy_write_queue.cc
File net/spdy/spdy_write_queue.cc (right):

https://codereview.chromium.org/13009012/diff/30001/net/spdy/spdy_write_queue...
net/spdy/spdy_write_queue.cc:48: DCHECK_EQ(stream->priority(), priority);
On 2013/03/28 15:51:04, Ryan Hamilton wrote:
> alternatively, you could have two Enqueue methods, one which takes a stream,
and
> one which takes a priority.  *shrug*  Might be cleaner, might be more code.

Eh, I think a single Enqueue is simpler. Added a comment re. stream->priority()
being required to equal priority.

https://codereview.chromium.org/13009012/diff/30001/net/spdy/spdy_write_queue...
net/spdy/spdy_write_queue.cc:56: if (!queue_[i].empty()) {
On 2013/03/28 15:51:04, Ryan Hamilton wrote:
> nit: I think I would write this as:
> if (queue_[i].empty())
>   continue;
> 
> early "return" ftw which lets you out-dent the rest of the block.

The thing is, I think that's more confusing because the loop body is itself an
early return! So I think it's clearer to keep the existing flow, even though it
is more indented, rather than have two different types of early-exits from the
loop.

https://codereview.chromium.org/13009012/diff/30001/net/spdy/spdy_write_queue...
net/spdy/spdy_write_queue.cc:91: queue_[stream->priority()].push_back(*it);
On 2013/03/28 15:51:04, Ryan Hamilton wrote:
> It looks like deque support an erase() method which returns an iterator to the
> next element after the erased element.  I think that might be better than
> reconstructing the deque.
> 
> Out of curiosity, would an std::list work as well as a deque here?

It does have erase(), but it's O(distance from end). However, there's no reason
to make a copy -- rewrote the loop to shift elements up and then truncate.

a std::list would also work, but I don't like it because of the extra node
overhead.

https://codereview.chromium.org/13009012/diff/30001/net/spdy/spdy_write_queue.h
File net/spdy/spdy_write_queue.h (right):

https://codereview.chromium.org/13009012/diff/30001/net/spdy/spdy_write_queue...
net/spdy/spdy_write_queue.h:55: class NET_EXPORT_PRIVATE SpdyWriteQueue {
On 2013/03/28 15:51:04, Ryan Hamilton wrote:
> Since this WriteQueue is only used by the Session, I think I would split the
> producer definitions out into spdy_frame_producer.h which spdy_stream would
> include, leaving only the producer in this file which would be included by
> spdy_session.

Done.

https://codereview.chromium.org/13009012/diff/30001/net/spdy/spdy_write_queue...
net/spdy/spdy_write_queue.h:62: // producer is associated with the session.
On 2013/03/28 15:51:04, Ryan Hamilton wrote:
> nit: if the frame is *not* associated with *a stream*.
> 
> I think?

Done.

https://codereview.chromium.org/13009012/diff/30001/net/spdy/spdy_write_queue...
net/spdy/spdy_write_queue.h:65: const scoped_refptr<SpdyStream>& stream);
On 2013/03/28 15:51:04, Ryan Hamilton wrote:
> out of curiosity, why is this a const scoped_refptr& and not a scoped_refptr?

it saves a ref inc/dec. habit I picked up from willchan.

https://codereview.chromium.org/13009012/diff/30001/net/spdy/spdy_write_queue...
net/spdy/spdy_write_queue.h:67: // Dequeues the next frame producer and its
associated
On 2013/03/28 15:51:04, Ryan Hamilton wrote:
> nit: Can you comment on the ordering guarantees of Dequeue.  In particular the
> fifo behavior within a priority, and priority order amongst priorities.  You
> mention the ordering at the class comment, but it think it would be helpful to
> mention here, since the ordering really comes into play here. 

Done.

[Ryan Hamilton, 2013-04-08 16:17:14]

lgtm

https://codereview.chromium.org/13009012/diff/30001/net/spdy/spdy_write_queue.cc
File net/spdy/spdy_write_queue.cc (right):

https://codereview.chromium.org/13009012/diff/30001/net/spdy/spdy_write_queue...
net/spdy/spdy_write_queue.cc:91: queue_[stream->priority()].push_back(*it);
On 2013/04/06 01:17:48, akalin wrote:
> On 2013/03/28 15:51:04, Ryan Hamilton wrote:
> > It looks like deque support an erase() method which returns an iterator to
the
> > next element after the erased element.  I think that might be better than
> > reconstructing the deque.
> > 
> > Out of curiosity, would an std::list work as well as a deque here?
> 
> It does have erase(), but it's O(distance from end). However, there's no
reason
> to make a copy -- rewrote the loop to shift elements up and then truncate.
> 
> a std::list would also work, but I don't like it because of the extra node
> overhead.

Good to know!  I'm unfamiliar with the internal list impl.  Can you say more?

[akalin, 2013-04-08 21:13:47]

On 2013/04/08 16:17:14, Ryan Hamilton wrote:
> Good to know!  I'm unfamiliar with the internal list impl.  Can you say more?

Oh, I was just referring to std::list being a doubly-linked list, so each for
each element in std::list there's a node object allocated for it with 2 pointers
of overhead. There's no compelling reason to use it over std::deque in this case
(and there rarely is in general, in my experience) so I'd rather go with deque,
which is basically an array of fixed-sized-T-arrays.

[commit-bot: I haz the power, 2013-04-09 00:23:32]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/akalin@chromium.org/13009012/43001

[akalin, 2013-04-09 00:50:29]

Committed patchset #5 manually as r192975 (presubmit successful).

[akalin, 2013-04-13 06:41:35]

On 2013/04/09 00:50:29, akalin wrote:
> Committed patchset #5 manually as r192975 (presubmit successful).

Latest patch set fixes the use-after-free described in 230259. It also replaces
a use of Unretained with GetWeakPtr().

I have no easy way of testing the fix locally, so I'll just recommit and watch
the ChromeOS ASAN bot.

[commit-bot: I haz the power, 2013-04-13 06:41:54]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/akalin@chromium.org/13009012/71001

[commit-bot: I haz the power, 2013-04-13 06:42:33]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/akalin@chromium.org/13009012/71001

[commit-bot: I haz the power, 2013-04-13 12:18:17]

Change committed as 194102