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 5package hpack 6 7import ( 8 "fmt" 9) 10 11// headerFieldTable implements a list of HeaderFields. 12// This is used to implement the static and dynamic tables. 13type 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 41type pairNameValue struct { 42 name, value string 43} 44 45func (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. 51func (t *headerFieldTable) len() int { 52 return len(t.ents) 53} 54 55// addEntry adds a new entry. 56func (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. 64func (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. 103func (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. 117func (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 129var staticTable = newStaticTable() 130var 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 194func newStaticTable() *headerFieldTable { 195 t := &headerFieldTable{} 196 t.init() 197 for _, e := range staticTableEntries[:] { 198 t.addEntry(e) 199 } 200 return t 201} 202 203var 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 462var 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} 480