hpack.go

     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  
     5  // Package hpack implements HPACK, a compression format for
     6  // efficiently representing HTTP header fields in the context of HTTP/2.
     7  //
     8  // See http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-09
     9  package hpack
    10  
    11  import (
    12  	"bytes"
    13  	"errors"
    14  	"fmt"
    15  )
    16  
    17  // A DecodingError is something the spec defines as a decoding error.
    18  type DecodingError struct {
    19  	Err error
    20  }
    21  
    22  func (de DecodingError) Error() string {
    23  	return fmt.Sprintf("decoding error: %v", de.Err)
    24  }
    25  
    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
    29  
    30  func (e InvalidIndexError) Error() string {
    31  	return fmt.Sprintf("invalid indexed representation index %d", int(e))
    32  }
    33  
    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 {
    37  	Name, Value string
    38  
    39  	// Sensitive means that this header field should never be
    40  	// indexed.
    41  	Sensitive bool
    42  }
    43  
    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,
    47  // though.
    48  func (hf HeaderField) IsPseudo() bool {
    49  	return len(hf.Name) != 0 && hf.Name[0] == ':'
    50  }
    51  
    52  func (hf HeaderField) String() string {
    53  	var suffix string
    54  	if hf.Sensitive {
    55  		suffix = " (sensitive)"
    56  	}
    57  	return fmt.Sprintf("header field %q = %q%s", hf.Name, hf.Value, suffix)
    58  }
    59  
    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."
    69  
    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
    73  	// it.
    74  	return uint32(len(hf.Name) + len(hf.Value) + 32)
    75  }
    76  
    77  // A Decoder is the decoding context for incremental processing of
    78  // header blocks.
    79  type Decoder struct {
    80  	dynTab dynamicTable
    81  	emit   func(f HeaderField)
    82  
    83  	emitEnabled bool // whether calls to emit are enabled
    84  	maxStrLen   int  // 0 means unlimited
    85  
    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
    91  
    92  	// saveBuf is previous data passed to Write which we weren't able
    93  	// to fully parse before. Unlike buf, we own this data.
    94  	saveBuf bytes.Buffer
    95  
    96  	firstField bool // processing the first field of the header block
    97  }
    98  
    99  // NewDecoder returns a new decoder with the provided maximum dynamic
   100  // table size. The emitFunc will be called for each valid field
   101  // parsed, in the same goroutine as calls to Write, before Write returns.
   102  func NewDecoder(maxDynamicTableSize uint32, emitFunc func(f HeaderField)) *Decoder {
   103  	d := &Decoder{
   104  		emit:        emitFunc,
   105  		emitEnabled: true,
   106  		firstField:  true,
   107  	}
   108  	d.dynTab.table.init()
   109  	d.dynTab.allowedMaxSize = maxDynamicTableSize
   110  	d.dynTab.setMaxSize(maxDynamicTableSize)
   111  	return d
   112  }
   113  
   114  // ErrStringLength is returned by Decoder.Write when the max string length
   115  // (as configured by Decoder.SetMaxStringLength) would be violated.
   116  var ErrStringLength = errors.New("hpack: string too long")
   117  
   118  // SetMaxStringLength sets the maximum size of a HeaderField name or
   119  // value string. If a string exceeds this length (even after any
   120  // decompression), Write will return ErrStringLength.
   121  // A value of 0 means unlimited and is the default from NewDecoder.
   122  func (d *Decoder) SetMaxStringLength(n int) {
   123  	d.maxStrLen = n
   124  }
   125  
   126  // SetEmitFunc changes the callback used when new header fields
   127  // are decoded.
   128  // It must be non-nil. It does not affect EmitEnabled.
   129  func (d *Decoder) SetEmitFunc(emitFunc func(f HeaderField)) {
   130  	d.emit = emitFunc
   131  }
   132  
   133  // SetEmitEnabled controls whether the emitFunc provided to NewDecoder
   134  // should be called. The default is true.
   135  //
   136  // This facility exists to let servers enforce MAX_HEADER_LIST_SIZE
   137  // while still decoding and keeping in-sync with decoder state, but
   138  // without doing unnecessary decompression or generating unnecessary
   139  // garbage for header fields past the limit.
   140  func (d *Decoder) SetEmitEnabled(v bool) { d.emitEnabled = v }
   141  
   142  // EmitEnabled reports whether calls to the emitFunc provided to NewDecoder
   143  // are currently enabled. The default is true.
   144  func (d *Decoder) EmitEnabled() bool { return d.emitEnabled }
   145  
   146  // TODO: add method *Decoder.Reset(maxSize, emitFunc) to let callers re-use Decoders and their
   147  // underlying buffers for garbage reasons.
   148  
   149  func (d *Decoder) SetMaxDynamicTableSize(v uint32) {
   150  	d.dynTab.setMaxSize(v)
   151  }
   152  
   153  // SetAllowedMaxDynamicTableSize sets the upper bound that the encoded
   154  // stream (via dynamic table size updates) may set the maximum size
   155  // to.
   156  func (d *Decoder) SetAllowedMaxDynamicTableSize(v uint32) {
   157  	d.dynTab.allowedMaxSize = v
   158  }
   159  
   160  type dynamicTable struct {
   161  	// http://http2.github.io/http2-spec/compression.html#rfc.section.2.3.2
   162  	table          headerFieldTable
   163  	size           uint32 // in bytes
   164  	maxSize        uint32 // current maxSize
   165  	allowedMaxSize uint32 // maxSize may go up to this, inclusive
   166  }
   167  
   168  func (dt *dynamicTable) setMaxSize(v uint32) {
   169  	dt.maxSize = v
   170  	dt.evict()
   171  }
   172  
   173  func (dt *dynamicTable) add(f HeaderField) {
   174  	dt.table.addEntry(f)
   175  	dt.size += f.Size()
   176  	dt.evict()
   177  }
   178  
   179  // If we're too big, evict old stuff.
   180  func (dt *dynamicTable) evict() {
   181  	var n int
   182  	for dt.size > dt.maxSize && n < dt.table.len() {
   183  		dt.size -= dt.table.ents[n].Size()
   184  		n++
   185  	}
   186  	dt.table.evictOldest(n)
   187  }
   188  
   189  func (d *Decoder) maxTableIndex() int {
   190  	// This should never overflow. RFC 7540 Section 6.5.2 limits the size of
   191  	// the dynamic table to 2^32 bytes, where each entry will occupy more than
   192  	// one byte. Further, the staticTable has a fixed, small length.
   193  	return d.dynTab.table.len() + staticTable.len()
   194  }
   195  
   196  func (d *Decoder) at(i uint64) (hf HeaderField, ok bool) {
   197  	// See Section 2.3.3.
   198  	if i == 0 {
   199  		return
   200  	}
   201  	if i <= uint64(staticTable.len()) {
   202  		return staticTable.ents[i-1], true
   203  	}
   204  	if i > uint64(d.maxTableIndex()) {
   205  		return
   206  	}
   207  	// In the dynamic table, newer entries have lower indices.
   208  	// However, dt.ents[0] is the oldest entry. Hence, dt.ents is
   209  	// the reversed dynamic table.
   210  	dt := d.dynTab.table
   211  	return dt.ents[dt.len()-(int(i)-staticTable.len())], true
   212  }
   213  
   214  // Decode decodes an entire block.
   215  //
   216  // TODO: remove this method and make it incremental later? This is
   217  // easier for debugging now.
   218  func (d *Decoder) DecodeFull(p []byte) ([]HeaderField, error) {
   219  	var hf []HeaderField
   220  	saveFunc := d.emit
   221  	defer func() { d.emit = saveFunc }()
   222  	d.emit = func(f HeaderField) { hf = append(hf, f) }
   223  	if _, err := d.Write(p); err != nil {
   224  		return nil, err
   225  	}
   226  	if err := d.Close(); err != nil {
   227  		return nil, err
   228  	}
   229  	return hf, nil
   230  }
   231  
   232  // Close declares that the decoding is complete and resets the Decoder
   233  // to be reused again for a new header block. If there is any remaining
   234  // data in the decoder's buffer, Close returns an error.
   235  func (d *Decoder) Close() error {
   236  	if d.saveBuf.Len() > 0 {
   237  		d.saveBuf.Reset()
   238  		return DecodingError{errors.New("truncated headers")}
   239  	}
   240  	d.firstField = true
   241  	return nil
   242  }
   243  
   244  func (d *Decoder) Write(p []byte) (n int, err error) {
   245  	if len(p) == 0 {
   246  		// Prevent state machine CPU attacks (making us redo
   247  		// work up to the point of finding out we don't have
   248  		// enough data)
   249  		return
   250  	}
   251  	// Only copy the data if we have to. Optimistically assume
   252  	// that p will contain a complete header block.
   253  	if d.saveBuf.Len() == 0 {
   254  		d.buf = p
   255  	} else {
   256  		d.saveBuf.Write(p)
   257  		d.buf = d.saveBuf.Bytes()
   258  		d.saveBuf.Reset()
   259  	}
   260  
   261  	for len(d.buf) > 0 {
   262  		err = d.parseHeaderFieldRepr()
   263  		if err == errNeedMore {
   264  			// Extra paranoia, making sure saveBuf won't
   265  			// get too large. All the varint and string
   266  			// reading code earlier should already catch
   267  			// overlong things and return ErrStringLength,
   268  			// but keep this as a last resort.
   269  			const varIntOverhead = 8 // conservative
   270  			if d.maxStrLen != 0 && int64(len(d.buf)) > 2*(int64(d.maxStrLen)+varIntOverhead) {
   271  				return 0, ErrStringLength
   272  			}
   273  			d.saveBuf.Write(d.buf)
   274  			return len(p), nil
   275  		}
   276  		d.firstField = false
   277  		if err != nil {
   278  			break
   279  		}
   280  	}
   281  	return len(p), err
   282  }
   283  
   284  // errNeedMore is an internal sentinel error value that means the
   285  // buffer is truncated and we need to read more data before we can
   286  // continue parsing.
   287  var errNeedMore = errors.New("need more data")
   288  
   289  type indexType int
   290  
   291  const (
   292  	indexedTrue indexType = iota
   293  	indexedFalse
   294  	indexedNever
   295  )
   296  
   297  func (v indexType) indexed() bool   { return v == indexedTrue }
   298  func (v indexType) sensitive() bool { return v == indexedNever }
   299  
   300  // returns errNeedMore if there isn't enough data available.
   301  // any other error is fatal.
   302  // consumes d.buf iff it returns nil.
   303  // precondition: must be called with len(d.buf) > 0
   304  func (d *Decoder) parseHeaderFieldRepr() error {
   305  	b := d.buf[0]
   306  	switch {
   307  	case b&128 != 0:
   308  		// Indexed representation.
   309  		// High bit set?
   310  		// http://http2.github.io/http2-spec/compression.html#rfc.section.6.1
   311  		return d.parseFieldIndexed()
   312  	case b&192 == 64:
   313  		// 6.2.1 Literal Header Field with Incremental Indexing
   314  		// 0b10xxxxxx: top two bits are 10
   315  		// http://http2.github.io/http2-spec/compression.html#rfc.section.6.2.1
   316  		return d.parseFieldLiteral(6, indexedTrue)
   317  	case b&240 == 0:
   318  		// 6.2.2 Literal Header Field without Indexing
   319  		// 0b0000xxxx: top four bits are 0000
   320  		// http://http2.github.io/http2-spec/compression.html#rfc.section.6.2.2
   321  		return d.parseFieldLiteral(4, indexedFalse)
   322  	case b&240 == 16:
   323  		// 6.2.3 Literal Header Field never Indexed
   324  		// 0b0001xxxx: top four bits are 0001
   325  		// http://http2.github.io/http2-spec/compression.html#rfc.section.6.2.3
   326  		return d.parseFieldLiteral(4, indexedNever)
   327  	case b&224 == 32:
   328  		// 6.3 Dynamic Table Size Update
   329  		// Top three bits are '001'.
   330  		// http://http2.github.io/http2-spec/compression.html#rfc.section.6.3
   331  		return d.parseDynamicTableSizeUpdate()
   332  	}
   333  
   334  	return DecodingError{errors.New("invalid encoding")}
   335  }
   336  
   337  // (same invariants and behavior as parseHeaderFieldRepr)
   338  func (d *Decoder) parseFieldIndexed() error {
   339  	buf := d.buf
   340  	idx, buf, err := readVarInt(7, buf)
   341  	if err != nil {
   342  		return err
   343  	}
   344  	hf, ok := d.at(idx)
   345  	if !ok {
   346  		return DecodingError{InvalidIndexError(idx)}
   347  	}
   348  	d.buf = buf
   349  	return d.callEmit(HeaderField{Name: hf.Name, Value: hf.Value})
   350  }
   351  
   352  // (same invariants and behavior as parseHeaderFieldRepr)
   353  func (d *Decoder) parseFieldLiteral(n uint8, it indexType) error {
   354  	buf := d.buf
   355  	nameIdx, buf, err := readVarInt(n, buf)
   356  	if err != nil {
   357  		return err
   358  	}
   359  
   360  	var hf HeaderField
   361  	wantStr := d.emitEnabled || it.indexed()
   362  	if nameIdx > 0 {
   363  		ihf, ok := d.at(nameIdx)
   364  		if !ok {
   365  			return DecodingError{InvalidIndexError(nameIdx)}
   366  		}
   367  		hf.Name = ihf.Name
   368  	} else {
   369  		hf.Name, buf, err = d.readString(buf, wantStr)
   370  		if err != nil {
   371  			return err
   372  		}
   373  	}
   374  	hf.Value, buf, err = d.readString(buf, wantStr)
   375  	if err != nil {
   376  		return err
   377  	}
   378  	d.buf = buf
   379  	if it.indexed() {
   380  		d.dynTab.add(hf)
   381  	}
   382  	hf.Sensitive = it.sensitive()
   383  	return d.callEmit(hf)
   384  }
   385  
   386  func (d *Decoder) callEmit(hf HeaderField) error {
   387  	if d.maxStrLen != 0 {
   388  		if len(hf.Name) > d.maxStrLen || len(hf.Value) > d.maxStrLen {
   389  			return ErrStringLength
   390  		}
   391  	}
   392  	if d.emitEnabled {
   393  		d.emit(hf)
   394  	}
   395  	return nil
   396  }
   397  
   398  // (same invariants and behavior as parseHeaderFieldRepr)
   399  func (d *Decoder) parseDynamicTableSizeUpdate() error {
   400  	// RFC 7541, sec 4.2: This dynamic table size update MUST occur at the
   401  	// beginning of the first header block following the change to the dynamic table size.
   402  	if !d.firstField && d.dynTab.size > 0 {
   403  		return DecodingError{errors.New("dynamic table size update MUST occur at the beginning of a header block")}
   404  	}
   405  
   406  	buf := d.buf
   407  	size, buf, err := readVarInt(5, buf)
   408  	if err != nil {
   409  		return err
   410  	}
   411  	if size > uint64(d.dynTab.allowedMaxSize) {
   412  		return DecodingError{errors.New("dynamic table size update too large")}
   413  	}
   414  	d.dynTab.setMaxSize(uint32(size))
   415  	d.buf = buf
   416  	return nil
   417  }
   418  
   419  var errVarintOverflow = DecodingError{errors.New("varint integer overflow")}
   420  
   421  // readVarInt reads an unsigned variable length integer off the
   422  // beginning of p. n is the parameter as described in
   423  // http://http2.github.io/http2-spec/compression.html#rfc.section.5.1.
   424  //
   425  // n must always be between 1 and 8.
   426  //
   427  // The returned remain buffer is either a smaller suffix of p, or err != nil.
   428  // The error is errNeedMore if p doesn't contain a complete integer.
   429  func readVarInt(n byte, p []byte) (i uint64, remain []byte, err error) {
   430  	if n < 1 || n > 8 {
   431  		panic("bad n")
   432  	}
   433  	if len(p) == 0 {
   434  		return 0, p, errNeedMore
   435  	}
   436  	i = uint64(p[0])
   437  	if n < 8 {
   438  		i &= (1 << uint64(n)) - 1
   439  	}
   440  	if i < (1<<uint64(n))-1 {
   441  		return i, p[1:], nil
   442  	}
   443  
   444  	origP := p
   445  	p = p[1:]
   446  	var m uint64
   447  	for len(p) > 0 {
   448  		b := p[0]
   449  		p = p[1:]
   450  		i += uint64(b&127) << m
   451  		if b&128 == 0 {
   452  			return i, p, nil
   453  		}
   454  		m += 7
   455  		if m >= 63 { // TODO: proper overflow check. making this up.
   456  			return 0, origP, errVarintOverflow
   457  		}
   458  	}
   459  	return 0, origP, errNeedMore
   460  }
   461  
   462  // readString decodes an hpack string from p.
   463  //
   464  // wantStr is whether s will be used. If false, decompression and
   465  // []byte->string garbage are skipped if s will be ignored
   466  // anyway. This does mean that huffman decoding errors for non-indexed
   467  // strings past the MAX_HEADER_LIST_SIZE are ignored, but the server
   468  // is returning an error anyway, and because they're not indexed, the error
   469  // won't affect the decoding state.
   470  func (d *Decoder) readString(p []byte, wantStr bool) (s string, remain []byte, err error) {
   471  	if len(p) == 0 {
   472  		return "", p, errNeedMore
   473  	}
   474  	isHuff := p[0]&128 != 0
   475  	strLen, p, err := readVarInt(7, p)
   476  	if err != nil {
   477  		return "", p, err
   478  	}
   479  	if d.maxStrLen != 0 && strLen > uint64(d.maxStrLen) {
   480  		return "", nil, ErrStringLength
   481  	}
   482  	if uint64(len(p)) < strLen {
   483  		return "", p, errNeedMore
   484  	}
   485  	if !isHuff {
   486  		if wantStr {
   487  			s = string(p[:strLen])
   488  		}
   489  		return s, p[strLen:], nil
   490  	}
   491  
   492  	if wantStr {
   493  		buf := bufPool.Get().(*bytes.Buffer)
   494  		buf.Reset() // don't trust others
   495  		defer bufPool.Put(buf)
   496  		if err := huffmanDecode(buf, d.maxStrLen, p[:strLen]); err != nil {
   497  			buf.Reset()
   498  			return "", nil, err
   499  		}
   500  		s = buf.String()
   501  		buf.Reset() // be nice to GC
   502  	}
   503  	return s, p[strLen:], nil
   504  }
   505
View as plain text