tables.go 9.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479
  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
  5. import (
  6. "fmt"
  7. )
  8. // headerFieldTable implements a list of HeaderFields.
  9. // This is used to implement the static and dynamic tables.
  10. type headerFieldTable struct {
  11. // For static tables, entries are never evicted.
  12. //
  13. // For dynamic tables, entries are evicted from ents[0] and added to the end.
  14. // Each entry has a unique id that starts at one and increments for each
  15. // entry that is added. This unique id is stable across evictions, meaning
  16. // it can be used as a pointer to a specific entry. As in hpack, unique ids
  17. // are 1-based. The unique id for ents[k] is k + evictCount + 1.
  18. //
  19. // Zero is not a valid unique id.
  20. //
  21. // evictCount should not overflow in any remotely practical situation. In
  22. // practice, we will have one dynamic table per HTTP/2 connection. If we
  23. // assume a very powerful server that handles 1M QPS per connection and each
  24. // request adds (then evicts) 100 entries from the table, it would still take
  25. // 2M years for evictCount to overflow.
  26. ents []HeaderField
  27. evictCount uint64
  28. // byName maps a HeaderField name to the unique id of the newest entry with
  29. // the same name. See above for a definition of "unique id".
  30. byName map[string]uint64
  31. // byNameValue maps a HeaderField name/value pair to the unique id of the newest
  32. // entry with the same name and value. See above for a definition of "unique id".
  33. byNameValue map[pairNameValue]uint64
  34. }
  35. type pairNameValue struct {
  36. name, value string
  37. }
  38. func (t *headerFieldTable) init() {
  39. t.byName = make(map[string]uint64)
  40. t.byNameValue = make(map[pairNameValue]uint64)
  41. }
  42. // len reports the number of entries in the table.
  43. func (t *headerFieldTable) len() int {
  44. return len(t.ents)
  45. }
  46. // addEntry adds a new entry.
  47. func (t *headerFieldTable) addEntry(f HeaderField) {
  48. id := uint64(t.len()) + t.evictCount + 1
  49. t.byName[f.Name] = id
  50. t.byNameValue[pairNameValue{f.Name, f.Value}] = id
  51. t.ents = append(t.ents, f)
  52. }
  53. // evictOldest evicts the n oldest entries in the table.
  54. func (t *headerFieldTable) evictOldest(n int) {
  55. if n > t.len() {
  56. panic(fmt.Sprintf("evictOldest(%v) on table with %v entries", n, t.len()))
  57. }
  58. for k := 0; k < n; k++ {
  59. f := t.ents[k]
  60. id := t.evictCount + uint64(k) + 1
  61. if t.byName[f.Name] == id {
  62. delete(t.byName, f.Name)
  63. }
  64. if p := (pairNameValue{f.Name, f.Value}); t.byNameValue[p] == id {
  65. delete(t.byNameValue, p)
  66. }
  67. }
  68. copy(t.ents, t.ents[n:])
  69. for k := t.len() - n; k < t.len(); k++ {
  70. t.ents[k] = HeaderField{} // so strings can be garbage collected
  71. }
  72. t.ents = t.ents[:t.len()-n]
  73. if t.evictCount+uint64(n) < t.evictCount {
  74. panic("evictCount overflow")
  75. }
  76. t.evictCount += uint64(n)
  77. }
  78. // search finds f in the table. If there is no match, i is 0.
  79. // If both name and value match, i is the matched index and nameValueMatch
  80. // becomes true. If only name matches, i points to that index and
  81. // nameValueMatch becomes false.
  82. //
  83. // The returned index is a 1-based HPACK index. For dynamic tables, HPACK says
  84. // that index 1 should be the newest entry, but t.ents[0] is the oldest entry,
  85. // meaning t.ents is reversed for dynamic tables. Hence, when t is a dynamic
  86. // table, the return value i actually refers to the entry t.ents[t.len()-i].
  87. //
  88. // All tables are assumed to be a dynamic tables except for the global
  89. // staticTable pointer.
  90. //
  91. // See Section 2.3.3.
  92. func (t *headerFieldTable) search(f HeaderField) (i uint64, nameValueMatch bool) {
  93. if !f.Sensitive {
  94. if id := t.byNameValue[pairNameValue{f.Name, f.Value}]; id != 0 {
  95. return t.idToIndex(id), true
  96. }
  97. }
  98. if id := t.byName[f.Name]; id != 0 {
  99. return t.idToIndex(id), false
  100. }
  101. return 0, false
  102. }
  103. // idToIndex converts a unique id to an HPACK index.
  104. // See Section 2.3.3.
  105. func (t *headerFieldTable) idToIndex(id uint64) uint64 {
  106. if id <= t.evictCount {
  107. panic(fmt.Sprintf("id (%v) <= evictCount (%v)", id, t.evictCount))
  108. }
  109. k := id - t.evictCount - 1 // convert id to an index t.ents[k]
  110. if t != staticTable {
  111. return uint64(t.len()) - k // dynamic table
  112. }
  113. return k + 1
  114. }
  115. // http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-07#appendix-B
  116. var staticTable = newStaticTable()
  117. var staticTableEntries = [...]HeaderField{
  118. {Name: ":authority"},
  119. {Name: ":method", Value: "GET"},
  120. {Name: ":method", Value: "POST"},
  121. {Name: ":path", Value: "/"},
  122. {Name: ":path", Value: "/index.html"},
  123. {Name: ":scheme", Value: "http"},
  124. {Name: ":scheme", Value: "https"},
  125. {Name: ":status", Value: "200"},
  126. {Name: ":status", Value: "204"},
  127. {Name: ":status", Value: "206"},
  128. {Name: ":status", Value: "304"},
  129. {Name: ":status", Value: "400"},
  130. {Name: ":status", Value: "404"},
  131. {Name: ":status", Value: "500"},
  132. {Name: "accept-charset"},
  133. {Name: "accept-encoding", Value: "gzip, deflate"},
  134. {Name: "accept-language"},
  135. {Name: "accept-ranges"},
  136. {Name: "accept"},
  137. {Name: "access-control-allow-origin"},
  138. {Name: "age"},
  139. {Name: "allow"},
  140. {Name: "authorization"},
  141. {Name: "cache-control"},
  142. {Name: "content-disposition"},
  143. {Name: "content-encoding"},
  144. {Name: "content-language"},
  145. {Name: "content-length"},
  146. {Name: "content-location"},
  147. {Name: "content-range"},
  148. {Name: "content-type"},
  149. {Name: "cookie"},
  150. {Name: "date"},
  151. {Name: "etag"},
  152. {Name: "expect"},
  153. {Name: "expires"},
  154. {Name: "from"},
  155. {Name: "host"},
  156. {Name: "if-match"},
  157. {Name: "if-modified-since"},
  158. {Name: "if-none-match"},
  159. {Name: "if-range"},
  160. {Name: "if-unmodified-since"},
  161. {Name: "last-modified"},
  162. {Name: "link"},
  163. {Name: "location"},
  164. {Name: "max-forwards"},
  165. {Name: "proxy-authenticate"},
  166. {Name: "proxy-authorization"},
  167. {Name: "range"},
  168. {Name: "referer"},
  169. {Name: "refresh"},
  170. {Name: "retry-after"},
  171. {Name: "server"},
  172. {Name: "set-cookie"},
  173. {Name: "strict-transport-security"},
  174. {Name: "transfer-encoding"},
  175. {Name: "user-agent"},
  176. {Name: "vary"},
  177. {Name: "via"},
  178. {Name: "www-authenticate"},
  179. }
  180. func newStaticTable() *headerFieldTable {
  181. t := &headerFieldTable{}
  182. t.init()
  183. for _, e := range staticTableEntries[:] {
  184. t.addEntry(e)
  185. }
  186. return t
  187. }
  188. var huffmanCodes = [256]uint32{
  189. 0x1ff8,
  190. 0x7fffd8,
  191. 0xfffffe2,
  192. 0xfffffe3,
  193. 0xfffffe4,
  194. 0xfffffe5,
  195. 0xfffffe6,
  196. 0xfffffe7,
  197. 0xfffffe8,
  198. 0xffffea,
  199. 0x3ffffffc,
  200. 0xfffffe9,
  201. 0xfffffea,
  202. 0x3ffffffd,
  203. 0xfffffeb,
  204. 0xfffffec,
  205. 0xfffffed,
  206. 0xfffffee,
  207. 0xfffffef,
  208. 0xffffff0,
  209. 0xffffff1,
  210. 0xffffff2,
  211. 0x3ffffffe,
  212. 0xffffff3,
  213. 0xffffff4,
  214. 0xffffff5,
  215. 0xffffff6,
  216. 0xffffff7,
  217. 0xffffff8,
  218. 0xffffff9,
  219. 0xffffffa,
  220. 0xffffffb,
  221. 0x14,
  222. 0x3f8,
  223. 0x3f9,
  224. 0xffa,
  225. 0x1ff9,
  226. 0x15,
  227. 0xf8,
  228. 0x7fa,
  229. 0x3fa,
  230. 0x3fb,
  231. 0xf9,
  232. 0x7fb,
  233. 0xfa,
  234. 0x16,
  235. 0x17,
  236. 0x18,
  237. 0x0,
  238. 0x1,
  239. 0x2,
  240. 0x19,
  241. 0x1a,
  242. 0x1b,
  243. 0x1c,
  244. 0x1d,
  245. 0x1e,
  246. 0x1f,
  247. 0x5c,
  248. 0xfb,
  249. 0x7ffc,
  250. 0x20,
  251. 0xffb,
  252. 0x3fc,
  253. 0x1ffa,
  254. 0x21,
  255. 0x5d,
  256. 0x5e,
  257. 0x5f,
  258. 0x60,
  259. 0x61,
  260. 0x62,
  261. 0x63,
  262. 0x64,
  263. 0x65,
  264. 0x66,
  265. 0x67,
  266. 0x68,
  267. 0x69,
  268. 0x6a,
  269. 0x6b,
  270. 0x6c,
  271. 0x6d,
  272. 0x6e,
  273. 0x6f,
  274. 0x70,
  275. 0x71,
  276. 0x72,
  277. 0xfc,
  278. 0x73,
  279. 0xfd,
  280. 0x1ffb,
  281. 0x7fff0,
  282. 0x1ffc,
  283. 0x3ffc,
  284. 0x22,
  285. 0x7ffd,
  286. 0x3,
  287. 0x23,
  288. 0x4,
  289. 0x24,
  290. 0x5,
  291. 0x25,
  292. 0x26,
  293. 0x27,
  294. 0x6,
  295. 0x74,
  296. 0x75,
  297. 0x28,
  298. 0x29,
  299. 0x2a,
  300. 0x7,
  301. 0x2b,
  302. 0x76,
  303. 0x2c,
  304. 0x8,
  305. 0x9,
  306. 0x2d,
  307. 0x77,
  308. 0x78,
  309. 0x79,
  310. 0x7a,
  311. 0x7b,
  312. 0x7ffe,
  313. 0x7fc,
  314. 0x3ffd,
  315. 0x1ffd,
  316. 0xffffffc,
  317. 0xfffe6,
  318. 0x3fffd2,
  319. 0xfffe7,
  320. 0xfffe8,
  321. 0x3fffd3,
  322. 0x3fffd4,
  323. 0x3fffd5,
  324. 0x7fffd9,
  325. 0x3fffd6,
  326. 0x7fffda,
  327. 0x7fffdb,
  328. 0x7fffdc,
  329. 0x7fffdd,
  330. 0x7fffde,
  331. 0xffffeb,
  332. 0x7fffdf,
  333. 0xffffec,
  334. 0xffffed,
  335. 0x3fffd7,
  336. 0x7fffe0,
  337. 0xffffee,
  338. 0x7fffe1,
  339. 0x7fffe2,
  340. 0x7fffe3,
  341. 0x7fffe4,
  342. 0x1fffdc,
  343. 0x3fffd8,
  344. 0x7fffe5,
  345. 0x3fffd9,
  346. 0x7fffe6,
  347. 0x7fffe7,
  348. 0xffffef,
  349. 0x3fffda,
  350. 0x1fffdd,
  351. 0xfffe9,
  352. 0x3fffdb,
  353. 0x3fffdc,
  354. 0x7fffe8,
  355. 0x7fffe9,
  356. 0x1fffde,
  357. 0x7fffea,
  358. 0x3fffdd,
  359. 0x3fffde,
  360. 0xfffff0,
  361. 0x1fffdf,
  362. 0x3fffdf,
  363. 0x7fffeb,
  364. 0x7fffec,
  365. 0x1fffe0,
  366. 0x1fffe1,
  367. 0x3fffe0,
  368. 0x1fffe2,
  369. 0x7fffed,
  370. 0x3fffe1,
  371. 0x7fffee,
  372. 0x7fffef,
  373. 0xfffea,
  374. 0x3fffe2,
  375. 0x3fffe3,
  376. 0x3fffe4,
  377. 0x7ffff0,
  378. 0x3fffe5,
  379. 0x3fffe6,
  380. 0x7ffff1,
  381. 0x3ffffe0,
  382. 0x3ffffe1,
  383. 0xfffeb,
  384. 0x7fff1,
  385. 0x3fffe7,
  386. 0x7ffff2,
  387. 0x3fffe8,
  388. 0x1ffffec,
  389. 0x3ffffe2,
  390. 0x3ffffe3,
  391. 0x3ffffe4,
  392. 0x7ffffde,
  393. 0x7ffffdf,
  394. 0x3ffffe5,
  395. 0xfffff1,
  396. 0x1ffffed,
  397. 0x7fff2,
  398. 0x1fffe3,
  399. 0x3ffffe6,
  400. 0x7ffffe0,
  401. 0x7ffffe1,
  402. 0x3ffffe7,
  403. 0x7ffffe2,
  404. 0xfffff2,
  405. 0x1fffe4,
  406. 0x1fffe5,
  407. 0x3ffffe8,
  408. 0x3ffffe9,
  409. 0xffffffd,
  410. 0x7ffffe3,
  411. 0x7ffffe4,
  412. 0x7ffffe5,
  413. 0xfffec,
  414. 0xfffff3,
  415. 0xfffed,
  416. 0x1fffe6,
  417. 0x3fffe9,
  418. 0x1fffe7,
  419. 0x1fffe8,
  420. 0x7ffff3,
  421. 0x3fffea,
  422. 0x3fffeb,
  423. 0x1ffffee,
  424. 0x1ffffef,
  425. 0xfffff4,
  426. 0xfffff5,
  427. 0x3ffffea,
  428. 0x7ffff4,
  429. 0x3ffffeb,
  430. 0x7ffffe6,
  431. 0x3ffffec,
  432. 0x3ffffed,
  433. 0x7ffffe7,
  434. 0x7ffffe8,
  435. 0x7ffffe9,
  436. 0x7ffffea,
  437. 0x7ffffeb,
  438. 0xffffffe,
  439. 0x7ffffec,
  440. 0x7ffffed,
  441. 0x7ffffee,
  442. 0x7ffffef,
  443. 0x7fffff0,
  444. 0x3ffffee,
  445. }
  446. var huffmanCodeLen = [256]uint8{
  447. 13, 23, 28, 28, 28, 28, 28, 28, 28, 24, 30, 28, 28, 30, 28, 28,
  448. 28, 28, 28, 28, 28, 28, 30, 28, 28, 28, 28, 28, 28, 28, 28, 28,
  449. 6, 10, 10, 12, 13, 6, 8, 11, 10, 10, 8, 11, 8, 6, 6, 6,
  450. 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 7, 8, 15, 6, 12, 10,
  451. 13, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  452. 7, 7, 7, 7, 7, 7, 7, 7, 8, 7, 8, 13, 19, 13, 14, 6,
  453. 15, 5, 6, 5, 6, 5, 6, 6, 6, 5, 7, 7, 6, 6, 6, 5,
  454. 6, 7, 6, 5, 5, 6, 7, 7, 7, 7, 7, 15, 11, 14, 13, 28,
  455. 20, 22, 20, 20, 22, 22, 22, 23, 22, 23, 23, 23, 23, 23, 24, 23,
  456. 24, 24, 22, 23, 24, 23, 23, 23, 23, 21, 22, 23, 22, 23, 23, 24,
  457. 22, 21, 20, 22, 22, 23, 23, 21, 23, 22, 22, 24, 21, 22, 23, 23,
  458. 21, 21, 22, 21, 23, 22, 23, 23, 20, 22, 22, 22, 23, 22, 22, 23,
  459. 26, 26, 20, 19, 22, 23, 22, 25, 26, 26, 26, 27, 27, 26, 24, 25,
  460. 19, 21, 26, 27, 27, 26, 27, 24, 21, 21, 26, 26, 28, 27, 27, 27,
  461. 20, 24, 20, 21, 22, 21, 21, 23, 22, 22, 25, 25, 24, 24, 26, 23,
  462. 26, 27, 26, 26, 27, 27, 27, 27, 27, 28, 27, 27, 27, 27, 27, 26,
  463. }