cmd/bpa-operator/vendor/golang.org/x/net/http2/hpack/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 }