hpack.go 14 KB

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