1// Copyright 2014 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package http2
6
7import "fmt"
8
9// WriteScheduler is the interface implemented by HTTP/2 write schedulers.
10// Methods are never called concurrently.
11type WriteScheduler interface {
12 // OpenStream opens a new stream in the write scheduler.
13 // It is illegal to call this with streamID=0 or with a streamID that is
14 // already open -- the call may panic.
15 OpenStream(streamID uint32, options OpenStreamOptions)
16
17 // CloseStream closes a stream in the write scheduler. Any frames queued on
18 // this stream should be discarded. It is illegal to call this on a stream
19 // that is not open -- the call may panic.
20 CloseStream(streamID uint32)
21
22 // AdjustStream adjusts the priority of the given stream. This may be called
23 // on a stream that has not yet been opened or has been closed. Note that
24 // RFC 7540 allows PRIORITY frames to be sent on streams in any state. See:
25 // https://tools.ietf.org/html/rfc7540#section-5.1
26 AdjustStream(streamID uint32, priority PriorityParam)
27
28 // Push queues a frame in the scheduler. In most cases, this will not be
29 // called with wr.StreamID()!=0 unless that stream is currently open. The one
30 // exception is RST_STREAM frames, which may be sent on idle or closed streams.
31 Push(wr FrameWriteRequest)
32
33 // Pop dequeues the next frame to write. Returns false if no frames can
34 // be written. Frames with a given wr.StreamID() are Pop'd in the same
35 // order they are Push'd, except RST_STREAM frames. No frames should be
36 // discarded except by CloseStream.
37 Pop() (wr FrameWriteRequest, ok bool)
38}
39
40// OpenStreamOptions specifies extra options for WriteScheduler.OpenStream.
41type OpenStreamOptions struct {
42 // PusherID is zero if the stream was initiated by the client. Otherwise,
43 // PusherID names the stream that pushed the newly opened stream.
44 PusherID uint32
45}
46
47// FrameWriteRequest is a request to write a frame.
48type FrameWriteRequest struct {
49 // write is the interface value that does the writing, once the
50 // WriteScheduler has selected this frame to write. The write
51 // functions are all defined in write.go.
52 write writeFramer
53
54 // stream is the stream on which this frame will be written.
55 // nil for non-stream frames like PING and SETTINGS.
56 // nil for RST_STREAM streams, which use the StreamError.StreamID field instead.
57 stream *stream
58
59 // done, if non-nil, must be a buffered channel with space for
60 // 1 message and is sent the return value from write (or an
61 // earlier error) when the frame has been written.
62 done chan error
63}
64
65// StreamID returns the id of the stream this frame will be written to.
66// 0 is used for non-stream frames such as PING and SETTINGS.
67func (wr FrameWriteRequest) StreamID() uint32 {
68 if wr.stream == nil {
69 if se, ok := wr.write.(StreamError); ok {
70 // (*serverConn).resetStream doesn't set
71 // stream because it doesn't necessarily have
72 // one. So special case this type of write
73 // message.
74 return se.StreamID
75 }
76 return 0
77 }
78 return wr.stream.id
79}
80
81// isControl reports whether wr is a control frame for MaxQueuedControlFrames
82// purposes. That includes non-stream frames and RST_STREAM frames.
83func (wr FrameWriteRequest) isControl() bool {
84 return wr.stream == nil
85}
86
87// DataSize returns the number of flow control bytes that must be consumed
88// to write this entire frame. This is 0 for non-DATA frames.
89func (wr FrameWriteRequest) DataSize() int {
90 if wd, ok := wr.write.(*writeData); ok {
91 return len(wd.p)
92 }
93 return 0
94}
95
96// Consume consumes min(n, available) bytes from this frame, where available
97// is the number of flow control bytes available on the stream. Consume returns
98// 0, 1, or 2 frames, where the integer return value gives the number of frames
99// returned.
100//
101// If flow control prevents consuming any bytes, this returns (_, _, 0). If
102// the entire frame was consumed, this returns (wr, _, 1). Otherwise, this
103// returns (consumed, rest, 2), where 'consumed' contains the consumed bytes and
104// 'rest' contains the remaining bytes. The consumed bytes are deducted from the
105// underlying stream's flow control budget.
106func (wr FrameWriteRequest) Consume(n int32) (FrameWriteRequest, FrameWriteRequest, int) {
107 var empty FrameWriteRequest
108
109 // Non-DATA frames are always consumed whole.
110 wd, ok := wr.write.(*writeData)
111 if !ok || len(wd.p) == 0 {
112 return wr, empty, 1
113 }
114
115 // Might need to split after applying limits.
116 allowed := wr.stream.flow.available()
117 if n < allowed {
118 allowed = n
119 }
120 if wr.stream.sc.maxFrameSize < allowed {
121 allowed = wr.stream.sc.maxFrameSize
122 }
123 if allowed <= 0 {
124 return empty, empty, 0
125 }
126 if len(wd.p) > int(allowed) {
127 wr.stream.flow.take(allowed)
128 consumed := FrameWriteRequest{
129 stream: wr.stream,
130 write: &writeData{
131 streamID: wd.streamID,
132 p: wd.p[:allowed],
133 // Even if the original had endStream set, there
134 // are bytes remaining because len(wd.p) > allowed,
135 // so we know endStream is false.
136 endStream: false,
137 },
138 // Our caller is blocking on the final DATA frame, not
139 // this intermediate frame, so no need to wait.
140 done: nil,
141 }
142 rest := FrameWriteRequest{
143 stream: wr.stream,
144 write: &writeData{
145 streamID: wd.streamID,
146 p: wd.p[allowed:],
147 endStream: wd.endStream,
148 },
149 done: wr.done,
150 }
151 return consumed, rest, 2
152 }
153
154 // The frame is consumed whole.
155 // NB: This cast cannot overflow because allowed is <= math.MaxInt32.
156 wr.stream.flow.take(int32(len(wd.p)))
157 return wr, empty, 1
158}
159
160// String is for debugging only.
161func (wr FrameWriteRequest) String() string {
162 var des string
163 if s, ok := wr.write.(fmt.Stringer); ok {
164 des = s.String()
165 } else {
166 des = fmt.Sprintf("%T", wr.write)
167 }
168 return fmt.Sprintf("[FrameWriteRequest stream=%d, ch=%v, writer=%v]", wr.StreamID(), wr.done != nil, des)
169}
170
171// replyToWriter sends err to wr.done and panics if the send must block
172// This does nothing if wr.done is nil.
173func (wr *FrameWriteRequest) replyToWriter(err error) {
174 if wr.done == nil {
175 return
176 }
177 select {
178 case wr.done <- err:
179 default:
180 panic(fmt.Sprintf("unbuffered done channel passed in for type %T", wr.write))
181 }
182 wr.write = nil // prevent use (assume it's tainted after wr.done send)
183}
184
185// writeQueue is used by implementations of WriteScheduler.
186type writeQueue struct {
187 s []FrameWriteRequest
188 prev, next *writeQueue
189}
190
191func (q *writeQueue) empty() bool { return len(q.s) == 0 }
192
193func (q *writeQueue) push(wr FrameWriteRequest) {
194 q.s = append(q.s, wr)
195}
196
197func (q *writeQueue) shift() FrameWriteRequest {
198 if len(q.s) == 0 {
199 panic("invalid use of queue")
200 }
201 wr := q.s[0]
202 // TODO: less copy-happy queue.
203 copy(q.s, q.s[1:])
204 q.s[len(q.s)-1] = FrameWriteRequest{}
205 q.s = q.s[:len(q.s)-1]
206 return wr
207}
208
209// consume consumes up to n bytes from q.s[0]. If the frame is
210// entirely consumed, it is removed from the queue. If the frame
211// is partially consumed, the frame is kept with the consumed
212// bytes removed. Returns true iff any bytes were consumed.
213func (q *writeQueue) consume(n int32) (FrameWriteRequest, bool) {
214 if len(q.s) == 0 {
215 return FrameWriteRequest{}, false
216 }
217 consumed, rest, numresult := q.s[0].Consume(n)
218 switch numresult {
219 case 0:
220 return FrameWriteRequest{}, false
221 case 1:
222 q.shift()
223 case 2:
224 q.s[0] = rest
225 }
226 return consumed, true
227}
228
229type writeQueuePool []*writeQueue
230
231// put inserts an unused writeQueue into the pool.
232func (p *writeQueuePool) put(q *writeQueue) {
233 for i := range q.s {
234 q.s[i] = FrameWriteRequest{}
235 }
236 q.s = q.s[:0]
237 *p = append(*p, q)
238}
239
240// get returns an empty writeQueue.
241func (p *writeQueuePool) get() *writeQueue {
242 ln := len(*p)
243 if ln == 0 {
244 return new(writeQueue)
245 }
246 x := ln - 1
247 q := (*p)[x]
248 (*p)[x] = nil
249 *p = (*p)[:x]
250 return q
251}