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}] = id
60 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 collected
82 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
100 // staticTable pointer.
102 // See Section 2.3.3.
103 func (t *headerFieldTable) search(f HeaderField) (i uint64, nameValueMatch bool) {
105 if id := t.byNameValue[pairNameValue{f.Name, f.Value}]; id != 0 {
106 return t.idToIndex(id), true
109 if id := t.byName[f.Name]; id != 0 {
110 return t.idToIndex(id), false
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))
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
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"},
150 {Name: "access-control-allow-origin"},
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"},
170 {Name: "if-modified-since"},
171 {Name: "if-none-match"},
173 {Name: "if-unmodified-since"},
174 {Name: "last-modified"},
177 {Name: "max-forwards"},
178 {Name: "proxy-authenticate"},
179 {Name: "proxy-authorization"},
183 {Name: "retry-after"},
185 {Name: "set-cookie"},
186 {Name: "strict-transport-security"},
187 {Name: "transfer-encoding"},
188 {Name: "user-agent"},
191 {Name: "www-authenticate"},
194 func newStaticTable() *headerFieldTable {
195 t := &headerFieldTable{}
197 for _, e := range staticTableEntries[:] {
203 var huffmanCodes = [256]uint32{
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,