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.
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.
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.
22
// Zero is not a valid unique id.
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.
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
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
41
type pairNameValue struct {45
func (t *headerFieldTable) init() {46
t.byName = make(map[string]uint64)
47
t.byNameValue = make(map[pairNameValue]uint64)
50
// len reports the number of entries in the table.
51
func (t *headerFieldTable) len() int {55
// addEntry adds a new entry.
56
func (t *headerFieldTable) addEntry(f HeaderField) {57
id := uint64(t.len()) + t.evictCount + 1
59
t.byNameValue[pairNameValue{f.Name, f.Value}] = id60
t.ents = append(t.ents, f)
63
// evictOldest evicts the n oldest entries in the table.
64
func (t *headerFieldTable) evictOldest(n int) {66
panic(fmt.Sprintf("evictOldest(%v) on table with %v entries", n, t.len()))68
for k := 0; k < n; k++ {70
id := t.evictCount + uint64(k) + 1
71
if t.byName[f.Name] == id {72
delete(t.byName, f.Name)
74
if p := (pairNameValue{f.Name, f.Value}); t.byNameValue[p] == id {75
delete(t.byNameValue, p)
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 collected82
t.ents = t.ents[:t.len()-n]
83
if t.evictCount+uint64(n) < t.evictCount {84
panic("evictCount overflow")86
t.evictCount += uint64(n)
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.
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].
99
// All tables are assumed to be a dynamic tables except for the global staticTable.
102
func (t *headerFieldTable) search(f HeaderField) (i uint64, nameValueMatch bool) {104
if id := t.byNameValue[pairNameValue{f.Name, f.Value}]; id != 0 {105
return t.idToIndex(id), true
108
if id := t.byName[f.Name]; id != 0 {109
return t.idToIndex(id), false
114
// idToIndex converts a unique id to an HPACK index.
116
func (t *headerFieldTable) idToIndex(id uint64) uint64 {117
if id <= t.evictCount {118
panic(fmt.Sprintf("id (%v) <= evictCount (%v)", id, t.evictCount))120
k := id - t.evictCount - 1 // convert id to an index t.ents[k]
121
if t != staticTable {122
return uint64(t.len()) - k // dynamic table
127
var huffmanCodes = [256]uint32{386
var huffmanCodeLen = [256]uint8{387
13, 23, 28, 28, 28, 28, 28, 28, 28, 24, 30, 28, 28, 30, 28, 28,
388
28, 28, 28, 28, 28, 28, 30, 28, 28, 28, 28, 28, 28, 28, 28, 28,
389
6, 10, 10, 12, 13, 6, 8, 11, 10, 10, 8, 11, 8, 6, 6, 6,
390
5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 7, 8, 15, 6, 12, 10,
391
13, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
392
7, 7, 7, 7, 7, 7, 7, 7, 8, 7, 8, 13, 19, 13, 14, 6,
393
15, 5, 6, 5, 6, 5, 6, 6, 6, 5, 7, 7, 6, 6, 6, 5,
394
6, 7, 6, 5, 5, 6, 7, 7, 7, 7, 7, 15, 11, 14, 13, 28,
395
20, 22, 20, 20, 22, 22, 22, 23, 22, 23, 23, 23, 23, 23, 24, 23,
396
24, 24, 22, 23, 24, 23, 23, 23, 23, 21, 22, 23, 22, 23, 23, 24,
397
22, 21, 20, 22, 22, 23, 23, 21, 23, 22, 22, 24, 21, 22, 23, 23,
398
21, 21, 22, 21, 23, 22, 23, 23, 20, 22, 22, 22, 23, 22, 22, 23,
399
26, 26, 20, 19, 22, 23, 22, 25, 26, 26, 26, 27, 27, 26, 24, 25,
400
19, 21, 26, 27, 27, 26, 27, 24, 21, 21, 26, 26, 28, 27, 27, 27,
401
20, 24, 20, 21, 22, 21, 21, 23, 22, 22, 25, 25, 24, 24, 26, 23,
402
26, 27, 26, 26, 27, 27, 27, 27, 27, 28, 27, 27, 27, 27, 27, 26,