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  	// https://httpwg.org/specs/rfc7541.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  	// https://httpwg.org/specs/rfc7541.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  // DecodeFull 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  		// https://httpwg.org/specs/rfc7541.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  		// https://httpwg.org/specs/rfc7541.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  		// https://httpwg.org/specs/rfc7541.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  		// https://httpwg.org/specs/rfc7541.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  		// https://httpwg.org/specs/rfc7541.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  	var undecodedName undecodedString
   363  	if nameIdx > 0 {
   364  		ihf, ok := d.at(nameIdx)
   365  		if !ok {
   366  			return DecodingError{InvalidIndexError(nameIdx)}
   367  		}
   368  		hf.Name = ihf.Name
   369  	} else {
   370  		undecodedName, buf, err = d.readString(buf)
   371  		if err != nil {
   372  			return err
   373  		}
   374  	}
   375  	undecodedValue, buf, err := d.readString(buf)
   376  	if err != nil {
   377  		return err
   378  	}
   379  	if wantStr {
   380  		if nameIdx <= 0 {
   381  			hf.Name, err = d.decodeString(undecodedName)
   382  			if err != nil {
   383  				return err
   384  			}
   385  		}
   386  		hf.Value, err = d.decodeString(undecodedValue)
   387  		if err != nil {
   388  			return err
   389  		}
   390  	}
   391  	d.buf = buf
   392  	if it.indexed() {
   393  		d.dynTab.add(hf)
   394  	}
   395  	hf.Sensitive = it.sensitive()
   396  	return d.callEmit(hf)
   397  }
   398  
   399  func (d *Decoder) callEmit(hf HeaderField) error {
   400  	if d.maxStrLen != 0 {
   401  		if len(hf.Name) > d.maxStrLen || len(hf.Value) > d.maxStrLen {
   402  			return ErrStringLength
   403  		}
   404  	}
   405  	if d.emitEnabled {
   406  		d.emit(hf)
   407  	}
   408  	return nil
   409  }
   410  
   411  // (same invariants and behavior as parseHeaderFieldRepr)
   412  func (d *Decoder) parseDynamicTableSizeUpdate() error {
   413  	// RFC 7541, sec 4.2: This dynamic table size update MUST occur at the
   414  	// beginning of the first header block following the change to the dynamic table size.
   415  	if !d.firstField && d.dynTab.size > 0 {
   416  		return DecodingError{errors.New("dynamic table size update MUST occur at the beginning of a header block")}
   417  	}
   418  
   419  	buf := d.buf
   420  	size, buf, err := readVarInt(5, buf)
   421  	if err != nil {
   422  		return err
   423  	}
   424  	if size > uint64(d.dynTab.allowedMaxSize) {
   425  		return DecodingError{errors.New("dynamic table size update too large")}
   426  	}
   427  	d.dynTab.setMaxSize(uint32(size))
   428  	d.buf = buf
   429  	return nil
   430  }
   431  
   432  var errVarintOverflow = DecodingError{errors.New("varint integer overflow")}
   433  
   434  // readVarInt reads an unsigned variable length integer off the
   435  // beginning of p. n is the parameter as described in
   436  // https://httpwg.org/specs/rfc7541.html#rfc.section.5.1.
   437  //
   438  // n must always be between 1 and 8.
   439  //
   440  // The returned remain buffer is either a smaller suffix of p, or err != nil.
   441  // The error is errNeedMore if p doesn't contain a complete integer.
   442  func readVarInt(n byte, p []byte) (i uint64, remain []byte, err error) {
   443  	if n < 1 || n > 8 {
   444  		panic("bad n")
   445  	}
   446  	if len(p) == 0 {
   447  		return 0, p, errNeedMore
   448  	}
   449  	i = uint64(p[0])
   450  	if n < 8 {
   451  		i &= (1 << uint64(n)) - 1
   452  	}
   453  	if i < (1<<uint64(n))-1 {
   454  		return i, p[1:], nil
   455  	}
   456  
   457  	origP := p
   458  	p = p[1:]
   459  	var m uint64
   460  	for len(p) > 0 {
   461  		b := p[0]
   462  		p = p[1:]
   463  		i += uint64(b&127) << m
   464  		if b&128 == 0 {
   465  			return i, p, nil
   466  		}
   467  		m += 7
   468  		if m >= 63 { // TODO: proper overflow check. making this up.
   469  			return 0, origP, errVarintOverflow
   470  		}
   471  	}
   472  	return 0, origP, errNeedMore
   473  }
   474  
   475  // readString reads an hpack string from p.
   476  //
   477  // It returns a reference to the encoded string data to permit deferring decode costs
   478  // until after the caller verifies all data is present.
   479  func (d *Decoder) readString(p []byte) (u undecodedString, remain []byte, err error) {
   480  	if len(p) == 0 {
   481  		return u, p, errNeedMore
   482  	}
   483  	isHuff := p[0]&128 != 0
   484  	strLen, p, err := readVarInt(7, p)
   485  	if err != nil {
   486  		return u, p, err
   487  	}
   488  	if d.maxStrLen != 0 && strLen > uint64(d.maxStrLen) {
   489  		// Returning an error here means Huffman decoding errors
   490  		// for non-indexed strings past the maximum string length
   491  		// are ignored, but the server is returning an error anyway
   492  		// and because the string is not indexed the error will not
   493  		// affect the decoding state.
   494  		return u, nil, ErrStringLength
   495  	}
   496  	if uint64(len(p)) < strLen {
   497  		return u, p, errNeedMore
   498  	}
   499  	u.isHuff = isHuff
   500  	u.b = p[:strLen]
   501  	return u, p[strLen:], nil
   502  }
   503  
   504  type undecodedString struct {
   505  	isHuff bool
   506  	b      []byte
   507  }
   508  
   509  func (d *Decoder) decodeString(u undecodedString) (string, error) {
   510  	if !u.isHuff {
   511  		return string(u.b), nil
   512  	}
   513  	buf := bufPool.Get().(*bytes.Buffer)
   514  	buf.Reset() // don't trust others
   515  	var s string
   516  	err := huffmanDecode(buf, d.maxStrLen, u.b)
   517  	if err == nil {
   518  		s = buf.String()
   519  	}
   520  	buf.Reset() // be nice to GC
   521  	bufPool.Put(buf)
   522  	return s, err
   523  }
   524
View as plain text