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 {
392 // RFC 7541, sec 4.2: This dynamic table size update MUST occur at the
393 // beginning of the first header block following the change to the dynamic table size.
394 if d.dynTab.size > 0 {
395 return DecodingError{errors.New("dynamic table size update MUST occur at the beginning of a header block")}
399 size, buf, err := readVarInt(5, buf)
403 if size > uint64(d.dynTab.allowedMaxSize) {
404 return DecodingError{errors.New("dynamic table size update too large")}
406 d.dynTab.setMaxSize(uint32(size))
411 var errVarintOverflow = DecodingError{errors.New("varint integer overflow")}
413 // readVarInt reads an unsigned variable length integer off the
414 // beginning of p. n is the parameter as described in
415 // http://http2.github.io/http2-spec/compression.html#rfc.section.5.1.
417 // n must always be between 1 and 8.
419 // The returned remain buffer is either a smaller suffix of p, or err != nil.
420 // The error is errNeedMore if p doesn't contain a complete integer.
421 func readVarInt(n byte, p []byte) (i uint64, remain []byte, err error) {
426 return 0, p, errNeedMore
430 i &= (1 << uint64(n)) - 1
432 if i < (1<<uint64(n))-1 {
442 i += uint64(b&127) << m
447 if m >= 63 { // TODO: proper overflow check. making this up.
448 return 0, origP, errVarintOverflow
451 return 0, origP, errNeedMore
454 // readString decodes an hpack string from p.
456 // wantStr is whether s will be used. If false, decompression and
457 // []byte->string garbage are skipped if s will be ignored
458 // anyway. This does mean that huffman decoding errors for non-indexed
459 // strings past the MAX_HEADER_LIST_SIZE are ignored, but the server
460 // is returning an error anyway, and because they're not indexed, the error
461 // won't affect the decoding state.
462 func (d *Decoder) readString(p []byte, wantStr bool) (s string, remain []byte, err error) {
464 return "", p, errNeedMore
466 isHuff := p[0]&128 != 0
467 strLen, p, err := readVarInt(7, p)
471 if d.maxStrLen != 0 && strLen > uint64(d.maxStrLen) {
472 return "", nil, ErrStringLength
474 if uint64(len(p)) < strLen {
475 return "", p, errNeedMore
479 s = string(p[:strLen])
481 return s, p[strLen:], nil
485 buf := bufPool.Get().(*bytes.Buffer)
486 buf.Reset() // don't trust others
487 defer bufPool.Put(buf)
488 if err := huffmanDecode(buf, d.maxStrLen, p[:strLen]); err != nil {
493 buf.Reset() // be nice to GC
495 return s, p[strLen:], nil