Matteo Scandolo | a428586 | 2020-12-01 18:10:10 -0800 | [diff] [blame] | 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 | } |