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