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.
5 // Package hpack implements HPACK, a compression format for
6 // efficiently representing HTTP header fields in the context of HTTP/2.
8 // See http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-09
17 // A DecodingError is something the spec defines as a decoding error.
18 type DecodingError
struct {
22 func (de DecodingError
) Error() string {
23 return fmt
.Sprintf("decoding error: %v", de
.Err
)
26 // An InvalidIndexError is returned when an encoder references a table
27 // entry before the static table or after the end of the dynamic table.
28 type InvalidIndexError
int
30 func (e InvalidIndexError
) Error() string {
31 return fmt
.Sprintf("invalid indexed representation index %d", int(e
))
34 // A HeaderField is a name-value pair. Both the name and value are
35 // treated as opaque sequences of octets.
36 type HeaderField
struct {
39 // Sensitive means that this header field should never be
44 // IsPseudo reports whether the header field is an http2 pseudo header.
45 // That is, it reports whether it starts with a colon.
46 // It is not otherwise guaranteed to be a valid pseudo header field,
48 func (hf HeaderField
) IsPseudo() bool {
49 return len(hf
.Name
) != 0 && hf
.Name
[0] == ':'
52 func (hf HeaderField
) String() string {
55 suffix
= " (sensitive)"
57 return fmt
.Sprintf("header field %q = %q%s", hf
.Name
, hf
.Value
, suffix
)
60 // Size returns the size of an entry per RFC 7541 section 4.1.
61 func (hf HeaderField
) Size() uint32 {
62 // http://http2.github.io/http2-spec/compression.html#rfc.section.4.1
63 // "The size of the dynamic table is the sum of the size of
64 // its entries. The size of an entry is the sum of its name's
65 // length in octets (as defined in Section 5.2), its value's
66 // length in octets (see Section 5.2), plus 32. The size of
67 // an entry is calculated using the length of the name and
68 // value without any Huffman encoding applied."
70 // This can overflow if somebody makes a large HeaderField
71 // Name and/or Value by hand, but we don't care, because that
72 // won't happen on the wire because the encoding doesn't allow
74 return uint32(len(hf
.Name
) + len(hf
.Value
) + 32)
77 // A Decoder is the decoding context for incremental processing of
81 emit
func(f HeaderField
)
83 emitEnabled
bool // whether calls to emit are enabled
84 maxStrLen
int // 0 means unlimited
86 // buf is the unparsed buffer. It's only written to
87 // saveBuf if it was truncated in the middle of a header
88 // block. Because it's usually not owned, we can only
89 // process it under Write.
90 buf
[]byte // not owned; only valid during Write
92 // saveBuf is previous data passed to Write which we weren't able
93 // to fully parse before. Unlike buf, we own this data.
97 // NewDecoder returns a new decoder with the provided maximum dynamic
98 // table size. The emitFunc will be called for each valid field
99 // parsed, in the same goroutine as calls to Write, before Write returns.
100 func NewDecoder(maxDynamicTableSize
uint32, emitFunc
func(f HeaderField
)) *Decoder
{
105 d
.dynTab
.table
.init()
106 d
.dynTab
.allowedMaxSize
= maxDynamicTableSize
107 d
.dynTab
.setMaxSize(maxDynamicTableSize
)
111 // ErrStringLength is returned by Decoder.Write when the max string length
112 // (as configured by Decoder.SetMaxStringLength) would be violated.
113 var ErrStringLength
= errors
.New("hpack: string too long")
115 // SetMaxStringLength sets the maximum size of a HeaderField name or
116 // value string. If a string exceeds this length (even after any
117 // decompression), Write will return ErrStringLength.
118 // A value of 0 means unlimited and is the default from NewDecoder.
119 func (d
*Decoder
) SetMaxStringLength(n
int) {
123 // SetEmitFunc changes the callback used when new header fields
125 // It must be non-nil. It does not affect EmitEnabled.
126 func (d
*Decoder
) SetEmitFunc(emitFunc
func(f HeaderField
)) {
130 // SetEmitEnabled controls whether the emitFunc provided to NewDecoder
131 // should be called. The default is true.
133 // This facility exists to let servers enforce MAX_HEADER_LIST_SIZE
134 // while still decoding and keeping in-sync with decoder state, but
135 // without doing unnecessary decompression or generating unnecessary
136 // garbage for header fields past the limit.
137 func (d
*Decoder
) SetEmitEnabled(v
bool) { d
.emitEnabled
= v
}
139 // EmitEnabled reports whether calls to the emitFunc provided to NewDecoder
140 // are currently enabled. The default is true.
141 func (d
*Decoder
) EmitEnabled() bool { return d
.emitEnabled
}
143 // TODO: add method *Decoder.Reset(maxSize, emitFunc) to let callers re-use Decoders and their
144 // underlying buffers for garbage reasons.
146 func (d
*Decoder
) SetMaxDynamicTableSize(v
uint32) {
147 d
.dynTab
.setMaxSize(v
)
150 // SetAllowedMaxDynamicTableSize sets the upper bound that the encoded
151 // stream (via dynamic table size updates) may set the maximum size
153 func (d
*Decoder
) SetAllowedMaxDynamicTableSize(v
uint32) {
154 d
.dynTab
.allowedMaxSize
= v
157 type dynamicTable
struct {
158 // http://http2.github.io/http2-spec/compression.html#rfc.section.2.3.2
159 table headerFieldTable
160 size
uint32 // in bytes
161 maxSize
uint32 // current maxSize
162 allowedMaxSize
uint32 // maxSize may go up to this, inclusive
165 func (dt
*dynamicTable
) setMaxSize(v
uint32) {
170 func (dt
*dynamicTable
) add(f HeaderField
) {
176 // If we're too big, evict old stuff.
177 func (dt
*dynamicTable
) evict() {
179 for dt
.size
> dt
.maxSize
&& n
< dt
.table
.len() {
180 dt
.size
-= dt
.table
.ents
[n
].Size()
183 dt
.table
.evictOldest(n
)
186 func (d
*Decoder
) maxTableIndex() int {
187 // This should never overflow. RFC 7540 Section 6.5.2 limits the size of
188 // the dynamic table to 2^32 bytes, where each entry will occupy more than
189 // one byte. Further, the staticTable has a fixed, small length.
190 return d
.dynTab
.table
.len() + staticTable
.len()
193 func (d
*Decoder
) at(i
uint64) (hf HeaderField
, ok
bool) {
194 // See Section 2.3.3.
198 if i
<= uint64(staticTable
.len()) {
199 return staticTable
.ents
[i
-1], true
201 if i
> uint64(d
.maxTableIndex()) {
204 // In the dynamic table, newer entries have lower indices.
205 // However, dt.ents[0] is the oldest entry. Hence, dt.ents is
206 // the reversed dynamic table.
208 return dt
.ents
[dt
.len()-(int(i
)-staticTable
.len())], true
211 // Decode decodes an entire block.
213 // TODO: remove this method and make it incremental later? This is
214 // easier for debugging now.
215 func (d
*Decoder
) DecodeFull(p
[]byte) ([]HeaderField
, error
) {
218 defer func() { d
.emit
= saveFunc
}()
219 d
.emit
= func(f HeaderField
) { hf
= append(hf
, f
) }
220 if _
, err
:= d
.Write(p
); err
!= nil {
223 if err
:= d
.Close(); err
!= nil {
229 func (d
*Decoder
) Close() error
{
230 if d
.saveBuf
.Len() > 0 {
232 return DecodingError
{errors
.New("truncated headers")}
237 func (d
*Decoder
) Write(p
[]byte) (n
int, err error
) {
239 // Prevent state machine CPU attacks (making us redo
240 // work up to the point of finding out we don't have
244 // Only copy the data if we have to. Optimistically assume
245 // that p will contain a complete header block.
246 if d
.saveBuf
.Len() == 0 {
250 d
.buf
= d
.saveBuf
.Bytes()
255 err
= d
.parseHeaderFieldRepr()
256 if err
== errNeedMore
{
257 // Extra paranoia, making sure saveBuf won't
258 // get too large. All the varint and string
259 // reading code earlier should already catch
260 // overlong things and return ErrStringLength,
261 // but keep this as a last resort.
262 const varIntOverhead
= 8 // conservative
263 if d
.maxStrLen
!= 0 && int64(len(d
.buf
)) > 2*(int64(d
.maxStrLen
)+varIntOverhead
) {
264 return 0, ErrStringLength
266 d
.saveBuf
.Write(d
.buf
)
276 // errNeedMore is an internal sentinel error value that means the
277 // buffer is truncated and we need to read more data before we can
279 var errNeedMore
= errors
.New("need more data")
284 indexedTrue indexType
= iota
289 func (v indexType
) indexed() bool { return v
== indexedTrue
}
290 func (v indexType
) sensitive() bool { return v
== indexedNever
}
292 // returns errNeedMore if there isn't enough data available.
293 // any other error is fatal.
294 // consumes d.buf iff it returns nil.
295 // precondition: must be called with len(d.buf) > 0
296 func (d
*Decoder
) parseHeaderFieldRepr() error
{
300 // Indexed representation.
302 // http://http2.github.io/http2-spec/compression.html#rfc.section.6.1
303 return d
.parseFieldIndexed()
305 // 6.2.1 Literal Header Field with Incremental Indexing
306 // 0b10xxxxxx: top two bits are 10
307 // http://http2.github.io/http2-spec/compression.html#rfc.section.6.2.1
308 return d
.parseFieldLiteral(6, indexedTrue
)
310 // 6.2.2 Literal Header Field without Indexing
311 // 0b0000xxxx: top four bits are 0000
312 // http://http2.github.io/http2-spec/compression.html#rfc.section.6.2.2
313 return d
.parseFieldLiteral(4, indexedFalse
)
315 // 6.2.3 Literal Header Field never Indexed
316 // 0b0001xxxx: top four bits are 0001
317 // http://http2.github.io/http2-spec/compression.html#rfc.section.6.2.3
318 return d
.parseFieldLiteral(4, indexedNever
)
320 // 6.3 Dynamic Table Size Update
321 // Top three bits are '001'.
322 // http://http2.github.io/http2-spec/compression.html#rfc.section.6.3
323 return d
.parseDynamicTableSizeUpdate()
326 return DecodingError
{errors
.New("invalid encoding")}
329 // (same invariants and behavior as parseHeaderFieldRepr)
330 func (d
*Decoder
) parseFieldIndexed() error
{
332 idx
, buf
, err
:= readVarInt(7, buf
)
338 return DecodingError
{InvalidIndexError(idx
)}
341 return d
.callEmit(HeaderField
{Name
: hf
.Name
, Value
: hf
.Value
})
344 // (same invariants and behavior as parseHeaderFieldRepr)
345 func (d
*Decoder
) parseFieldLiteral(n
uint8, it indexType
) error
{
347 nameIdx
, buf
, err
:= readVarInt(n
, buf
)
353 wantStr
:= d
.emitEnabled || it
.indexed()
355 ihf
, ok
:= d
.at(nameIdx
)
357 return DecodingError
{InvalidIndexError(nameIdx
)}
361 hf
.Name
, buf
, err
= d
.readString(buf
, wantStr
)
366 hf
.Value
, buf
, err
= d
.readString(buf
, wantStr
)
374 hf
.Sensitive
= it
.sensitive()
375 return d
.callEmit(hf
)
378 func (d
*Decoder
) callEmit(hf HeaderField
) error
{
379 if d
.maxStrLen
!= 0 {
380 if len(hf
.Name
) > d
.maxStrLen ||
len(hf
.Value
) > d
.maxStrLen
{
381 return ErrStringLength
390 // (same invariants and behavior as parseHeaderFieldRepr)
391 func (d
*Decoder
) parseDynamicTableSizeUpdate() error
{
393 size
, buf
, err
:= readVarInt(5, buf
)
397 if size
> uint64(d
.dynTab
.allowedMaxSize
) {
398 return DecodingError
{errors
.New("dynamic table size update too large")}
400 d
.dynTab
.setMaxSize(uint32(size
))
405 var errVarintOverflow
= DecodingError
{errors
.New("varint integer overflow")}
407 // readVarInt reads an unsigned variable length integer off the
408 // beginning of p. n is the parameter as described in
409 // http://http2.github.io/http2-spec/compression.html#rfc.section.5.1.
411 // n must always be between 1 and 8.
413 // The returned remain buffer is either a smaller suffix of p, or err != nil.
414 // The error is errNeedMore if p doesn't contain a complete integer.
415 func readVarInt(n
byte, p
[]byte) (i
uint64, remain
[]byte, err error
) {
420 return 0, p
, errNeedMore
424 i
&= (1 << uint64(n
)) - 1
426 if i
< (1<<uint64(n
))-1 {
436 i
+= uint64(b
&127) << m
441 if m
>= 63 { // TODO: proper overflow check. making this up.
442 return 0, origP
, errVarintOverflow
445 return 0, origP
, errNeedMore
448 // readString decodes an hpack string from p.
450 // wantStr is whether s will be used. If false, decompression and
451 // []byte->string garbage are skipped if s will be ignored
452 // anyway. This does mean that huffman decoding errors for non-indexed
453 // strings past the MAX_HEADER_LIST_SIZE are ignored, but the server
454 // is returning an error anyway, and because they're not indexed, the error
455 // won't affect the decoding state.
456 func (d
*Decoder
) readString(p
[]byte, wantStr
bool) (s
string, remain
[]byte, err error
) {
458 return "", p
, errNeedMore
460 isHuff
:= p
[0]&128 != 0
461 strLen
, p
, err
:= readVarInt(7, p
)
465 if d
.maxStrLen
!= 0 && strLen
> uint64(d
.maxStrLen
) {
466 return "", nil, ErrStringLength
468 if uint64(len(p
)) < strLen
{
469 return "", p
, errNeedMore
473 s
= string(p
[:strLen
])
475 return s
, p
[strLen
:], nil
479 buf
:= bufPool
.Get().(*bytes
.Buffer
)
480 buf
.Reset() // don't trust others
481 defer bufPool
.Put(buf
)
482 if err
:= huffmanDecode(buf
, d
.maxStrLen
, p
[:strLen
]); err
!= nil {
487 buf
.Reset() // be nice to GC
489 return s
, p
[strLen
:], nil