http2/hpack: speedup Encoder.searchTable
The previous algorithm was linear in the size of the table.
The new algorithm is O(1). The new algorithm should behave exactly
like the old algorthm, except for one unimportant change that
triggered small updates to tests in encode_test.go:
When encoding "Field: Value" where the table has two entries,
[0]={"Field", "X"} and [1]={"Field", "Y"}, we can encode the field
name using either table entry. Previously, we selected the oldest
entry, but now we select the newest entry. The new implementation
should actually generate very slightly better compression because
new entries are encoded with smaller integers than old entries, and
HPACK uses a varint encoding for integers where smaller integers
are encoded in fewer bytes.
I added a synthetic microbenchmark which shows a big speedup in
hpack.Encoder.searchTable:
BenchmarkEncoderSearchTable-40 100000 127440 ns/op # before
BenchmarkEncoderSearchTable-40 50000 25121 ns/op # after
Change-Id: Ib87d61b6415d9f0ff38874fe2a719b2f00351590
Reviewed-on: https://go-review.googlesource.com/37406
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
diff --git a/http2/hpack/encode.go b/http2/hpack/encode.go
index 395e1c2..54726c2 100644
--- a/http2/hpack/encode.go
+++ b/http2/hpack/encode.go
@@ -39,6 +39,7 @@
tableSizeUpdate: false,
w: w,
}
+ e.dynTab.table.init()
e.dynTab.setMaxSize(initialHeaderTableSize)
return e
}
@@ -88,24 +89,17 @@
// only name matches, i points to that index and nameValueMatch
// becomes false.
func (e *Encoder) searchTable(f HeaderField) (i uint64, nameValueMatch bool) {
- for idx, hf := range staticTable {
- if hf.Name != f.Name {
- continue
- }
- if i == 0 {
- i = uint64(idx + 1)
- }
- if f.Sensitive || hf.Value != f.Value {
- continue
- }
- return uint64(idx + 1), true
+ i, nameValueMatch = staticTable.search(f)
+ if nameValueMatch {
+ return i, true
}
- j, nameValueMatch := e.dynTab.search(f)
+ j, nameValueMatch := e.dynTab.table.search(f)
if nameValueMatch || (i == 0 && j != 0) {
- i = j + uint64(len(staticTable))
+ return j + uint64(staticTable.len()), nameValueMatch
}
- return
+
+ return i, false
}
// SetMaxDynamicTableSize changes the dynamic header table size to v.
diff --git a/http2/hpack/encode_test.go b/http2/hpack/encode_test.go
index 92286f3..05f12db 100644
--- a/http2/hpack/encode_test.go
+++ b/http2/hpack/encode_test.go
@@ -7,6 +7,8 @@
import (
"bytes"
"encoding/hex"
+ "fmt"
+ "math/rand"
"reflect"
"strings"
"testing"
@@ -101,17 +103,20 @@
wantMatch bool
}{
// Name and Value match
- {pair("foo", "bar"), uint64(len(staticTable) + 3), true},
- {pair("blake", "miz"), uint64(len(staticTable) + 2), true},
+ {pair("foo", "bar"), uint64(staticTable.len()) + 3, true},
+ {pair("blake", "miz"), uint64(staticTable.len()) + 2, true},
{pair(":method", "GET"), 2, true},
- // Only name match because Sensitive == true
- {HeaderField{":method", "GET", true}, 2, false},
+ // Only name match because Sensitive == true. This is allowed to match
+ // any ":method" entry. The current implementation uses the last entry
+ // added in newStaticTable.
+ {HeaderField{":method", "GET", true}, 3, false},
// Only Name matches
- {pair("foo", "..."), uint64(len(staticTable) + 3), false},
- {pair("blake", "..."), uint64(len(staticTable) + 2), false},
- {pair(":method", "..."), 2, false},
+ {pair("foo", "..."), uint64(staticTable.len()) + 3, false},
+ {pair("blake", "..."), uint64(staticTable.len()) + 2, false},
+ // As before, this is allowed to match any ":method" entry.
+ {pair(":method", "..."), 3, false},
// None match
{pair("foo-", "bar"), 0, false},
@@ -328,3 +333,54 @@
func removeSpace(s string) string {
return strings.Replace(s, " ", "", -1)
}
+
+func BenchmarkEncoderSearchTable(b *testing.B) {
+ e := NewEncoder(nil)
+
+ // A sample of possible header fields.
+ // This is not based on any actual data from HTTP/2 traces.
+ var possible []HeaderField
+ for _, f := range staticTable.ents {
+ if f.Value == "" {
+ possible = append(possible, f)
+ continue
+ }
+ // Generate 5 random values, except for cookie and set-cookie,
+ // which we know can have many values in practice.
+ num := 5
+ if f.Name == "cookie" || f.Name == "set-cookie" {
+ num = 25
+ }
+ for i := 0; i < num; i++ {
+ f.Value = fmt.Sprintf("%s-%d", f.Name, i)
+ possible = append(possible, f)
+ }
+ }
+ for k := 0; k < 10; k++ {
+ f := HeaderField{
+ Name: fmt.Sprintf("x-header-%d", k),
+ Sensitive: rand.Int()%2 == 0,
+ }
+ for i := 0; i < 5; i++ {
+ f.Value = fmt.Sprintf("%s-%d", f.Name, i)
+ possible = append(possible, f)
+ }
+ }
+
+ // Add a random sample to the dynamic table. This very loosely simulates
+ // a history of 100 requests with 20 header fields per request.
+ for r := 0; r < 100*20; r++ {
+ f := possible[rand.Int31n(int32(len(possible)))]
+ // Skip if this is in the staticTable verbatim.
+ if _, has := staticTable.search(f); !has {
+ e.dynTab.add(f)
+ }
+ }
+
+ b.ResetTimer()
+ for n := 0; n < b.N; n++ {
+ for _, f := range possible {
+ e.searchTable(f)
+ }
+ }
+}
diff --git a/http2/hpack/hpack.go b/http2/hpack/hpack.go
index d18be44..176644a 100644
--- a/http2/hpack/hpack.go
+++ b/http2/hpack/hpack.go
@@ -102,6 +102,7 @@
emit: emitFunc,
emitEnabled: true,
}
+ d.dynTab.table.init()
d.dynTab.allowedMaxSize = maxDynamicTableSize
d.dynTab.setMaxSize(maxDynamicTableSize)
return d
@@ -154,12 +155,9 @@
}
type dynamicTable struct {
- // ents is the FIFO described at
// http://http2.github.io/http2-spec/compression.html#rfc.section.2.3.2
- // The newest (low index) is append at the end, and items are
- // evicted from the front.
- ents []HeaderField
- size uint32
+ table headerFieldTable
+ size uint32 // in bytes
maxSize uint32 // current maxSize
allowedMaxSize uint32 // maxSize may go up to this, inclusive
}
@@ -169,77 +167,45 @@
dt.evict()
}
-// TODO: change dynamicTable to be a struct with a slice and a size int field,
-// per http://http2.github.io/http2-spec/compression.html#rfc.section.4.1:
-//
-//
-// Then make add increment the size. maybe the max size should move from Decoder to
-// dynamicTable and add should return an ok bool if there was enough space.
-//
-// Later we'll need a remove operation on dynamicTable.
-
func (dt *dynamicTable) add(f HeaderField) {
- dt.ents = append(dt.ents, f)
+ dt.table.addEntry(f)
dt.size += f.Size()
dt.evict()
}
-// If we're too big, evict old stuff (front of the slice)
+// If we're too big, evict old stuff.
func (dt *dynamicTable) evict() {
- base := dt.ents // keep base pointer of slice
- for dt.size > dt.maxSize {
- dt.size -= dt.ents[0].Size()
- dt.ents = dt.ents[1:]
+ var n int
+ for dt.size > dt.maxSize && n < dt.table.len() {
+ dt.size -= dt.table.ents[n].Size()
+ n++
}
-
- // Shift slice contents down if we evicted things.
- if len(dt.ents) != len(base) {
- copy(base, dt.ents)
- dt.ents = base[:len(dt.ents)]
- }
-}
-
-// Search searches f in the table. The return value i is 0 if there is
-// no name match. If there is name match or name/value match, i is the
-// index of that entry (1-based). If both name and value match,
-// nameValueMatch becomes true.
-func (dt *dynamicTable) search(f HeaderField) (i uint64, nameValueMatch bool) {
- l := len(dt.ents)
- for j := l - 1; j >= 0; j-- {
- ent := dt.ents[j]
- if ent.Name != f.Name {
- continue
- }
- if i == 0 {
- i = uint64(l - j)
- }
- if f.Sensitive {
- continue
- }
- if ent.Value != f.Value {
- continue
- }
- return uint64(l - j), true
- }
- return i, false
+ dt.table.evictOldest(n)
}
func (d *Decoder) maxTableIndex() int {
- return len(d.dynTab.ents) + len(staticTable)
+ // This should never overflow. RFC 7540 Section 6.5.2 limits the size of
+ // the dynamic table to 2^32 bytes, where each entry will occupy more than
+ // one byte. Further, the staticTable has a fixed, small length.
+ return d.dynTab.table.len() + staticTable.len()
}
func (d *Decoder) at(i uint64) (hf HeaderField, ok bool) {
- if i < 1 {
+ // See Section 2.3.3.
+ if i == 0 {
return
}
+ if i <= uint64(staticTable.len()) {
+ return staticTable.ents[i-1], true
+ }
if i > uint64(d.maxTableIndex()) {
return
}
- if i <= uint64(len(staticTable)) {
- return staticTable[i-1], true
- }
- dents := d.dynTab.ents
- return dents[len(dents)-(int(i)-len(staticTable))], true
+ // In the dynamic table, newer entries have lower indices.
+ // However, dt.ents[0] is the oldest entry. Hence, dt.ents is
+ // the reversed dynamic table.
+ dt := d.dynTab.table
+ return dt.ents[dt.len()-(int(i)-staticTable.len())], true
}
// Decode decodes an entire block.
diff --git a/http2/hpack/hpack_test.go b/http2/hpack/hpack_test.go
index 4c7b17b..c2f8fd1 100644
--- a/http2/hpack/hpack_test.go
+++ b/http2/hpack/hpack_test.go
@@ -5,117 +5,16 @@
package hpack
import (
- "bufio"
"bytes"
"encoding/hex"
"fmt"
"math/rand"
"reflect"
- "regexp"
- "strconv"
"strings"
"testing"
"time"
)
-func TestStaticTable(t *testing.T) {
- fromSpec := `
- +-------+-----------------------------+---------------+
- | 1 | :authority | |
- | 2 | :method | GET |
- | 3 | :method | POST |
- | 4 | :path | / |
- | 5 | :path | /index.html |
- | 6 | :scheme | http |
- | 7 | :scheme | https |
- | 8 | :status | 200 |
- | 9 | :status | 204 |
- | 10 | :status | 206 |
- | 11 | :status | 304 |
- | 12 | :status | 400 |
- | 13 | :status | 404 |
- | 14 | :status | 500 |
- | 15 | accept-charset | |
- | 16 | accept-encoding | gzip, deflate |
- | 17 | accept-language | |
- | 18 | accept-ranges | |
- | 19 | accept | |
- | 20 | access-control-allow-origin | |
- | 21 | age | |
- | 22 | allow | |
- | 23 | authorization | |
- | 24 | cache-control | |
- | 25 | content-disposition | |
- | 26 | content-encoding | |
- | 27 | content-language | |
- | 28 | content-length | |
- | 29 | content-location | |
- | 30 | content-range | |
- | 31 | content-type | |
- | 32 | cookie | |
- | 33 | date | |
- | 34 | etag | |
- | 35 | expect | |
- | 36 | expires | |
- | 37 | from | |
- | 38 | host | |
- | 39 | if-match | |
- | 40 | if-modified-since | |
- | 41 | if-none-match | |
- | 42 | if-range | |
- | 43 | if-unmodified-since | |
- | 44 | last-modified | |
- | 45 | link | |
- | 46 | location | |
- | 47 | max-forwards | |
- | 48 | proxy-authenticate | |
- | 49 | proxy-authorization | |
- | 50 | range | |
- | 51 | referer | |
- | 52 | refresh | |
- | 53 | retry-after | |
- | 54 | server | |
- | 55 | set-cookie | |
- | 56 | strict-transport-security | |
- | 57 | transfer-encoding | |
- | 58 | user-agent | |
- | 59 | vary | |
- | 60 | via | |
- | 61 | www-authenticate | |
- +-------+-----------------------------+---------------+
-`
- bs := bufio.NewScanner(strings.NewReader(fromSpec))
- re := regexp.MustCompile(`\| (\d+)\s+\| (\S+)\s*\| (\S(.*\S)?)?\s+\|`)
- for bs.Scan() {
- l := bs.Text()
- if !strings.Contains(l, "|") {
- continue
- }
- m := re.FindStringSubmatch(l)
- if m == nil {
- continue
- }
- i, err := strconv.Atoi(m[1])
- if err != nil {
- t.Errorf("Bogus integer on line %q", l)
- continue
- }
- if i < 1 || i > len(staticTable) {
- t.Errorf("Bogus index %d on line %q", i, l)
- continue
- }
- if got, want := staticTable[i-1].Name, m[2]; got != want {
- t.Errorf("header index %d name = %q; want %q", i, got, want)
- }
- if got, want := staticTable[i-1].Value, m[3]; got != want {
- t.Errorf("header index %d value = %q; want %q", i, got, want)
- }
- }
- if err := bs.Err(); err != nil {
- t.Error(err)
- }
-}
-
func (d *Decoder) mustAt(idx int) HeaderField {
if hf, ok := d.at(uint64(idx)); !ok {
panic(fmt.Sprintf("bogus index %d", idx))
@@ -132,10 +31,10 @@
}
d.dynTab.add(pair("foo", "bar"))
d.dynTab.add(pair("blake", "miz"))
- if got, want := at(len(staticTable)+1), (pair("blake", "miz")); got != want {
+ if got, want := at(staticTable.len()+1), (pair("blake", "miz")); got != want {
t.Errorf("at(dyn 1) = %v; want %v", got, want)
}
- if got, want := at(len(staticTable)+2), (pair("foo", "bar")); got != want {
+ if got, want := at(staticTable.len()+2), (pair("foo", "bar")); got != want {
t.Errorf("at(dyn 2) = %v; want %v", got, want)
}
if got, want := at(3), (pair(":method", "POST")); got != want {
@@ -143,41 +42,6 @@
}
}
-func TestDynamicTableSearch(t *testing.T) {
- dt := dynamicTable{}
- dt.setMaxSize(4096)
-
- dt.add(pair("foo", "bar"))
- dt.add(pair("blake", "miz"))
- dt.add(pair(":method", "GET"))
-
- tests := []struct {
- hf HeaderField
- wantI uint64
- wantMatch bool
- }{
- // Name and Value match
- {pair("foo", "bar"), 3, true},
- {pair(":method", "GET"), 1, true},
-
- // Only name match because of Sensitive == true
- {HeaderField{"blake", "miz", true}, 2, false},
-
- // Only Name matches
- {pair("foo", "..."), 3, false},
- {pair("blake", "..."), 2, false},
- {pair(":method", "..."), 1, false},
-
- // None match
- {pair("foo-", "bar"), 0, false},
- }
- for _, tt := range tests {
- if gotI, gotMatch := dt.search(tt.hf); gotI != tt.wantI || gotMatch != tt.wantMatch {
- t.Errorf("d.search(%+v) = %v, %v; want %v, %v", tt.hf, gotI, gotMatch, tt.wantI, tt.wantMatch)
- }
- }
-}
-
func TestDynamicTableSizeEvict(t *testing.T) {
d := NewDecoder(4096, nil)
if want := uint32(0); d.dynTab.size != want {
@@ -196,7 +60,7 @@
if want := uint32(6 + 32); d.dynTab.size != want {
t.Fatalf("after setMaxSize, size = %d; want %d", d.dynTab.size, want)
}
- if got, want := d.mustAt(len(staticTable)+1), (pair("foo", "bar")); got != want {
+ if got, want := d.mustAt(staticTable.len()+1), (pair("foo", "bar")); got != want {
t.Errorf("at(dyn 1) = %v; want %v", got, want)
}
add(pair("long", strings.Repeat("x", 500)))
@@ -255,9 +119,9 @@
}
func (dt *dynamicTable) reverseCopy() (hf []HeaderField) {
- hf = make([]HeaderField, len(dt.ents))
+ hf = make([]HeaderField, len(dt.table.ents))
for i := range hf {
- hf[i] = dt.ents[len(dt.ents)-1-i]
+ hf[i] = dt.table.ents[len(dt.table.ents)-1-i]
}
return
}
diff --git a/http2/hpack/tables.go b/http2/hpack/tables.go
index b9283a0..8701592 100644
--- a/http2/hpack/tables.go
+++ b/http2/hpack/tables.go
@@ -4,73 +4,199 @@
package hpack
+import (
+ "fmt"
+)
+
+// headerFieldTable implements a list of HeaderFields.
+// This is used to implement the static and dynamic tables.
+type headerFieldTable struct {
+ // For static tables, entries are never evicted.
+ //
+ // For dynamic tables, entries are evicted from ents[0] and added to the end.
+ // Each entry has a unique id that starts at one and increments for each
+ // entry that is added. This unique id is stable across evictions, meaning
+ // it can be used as a pointer to a specific entry. As in hpack, unique ids
+ // are 1-based. The unique id for ents[k] is k + evictCount + 1.
+ //
+ // Zero is not a valid unique id.
+ //
+ // evictCount should not overflow in any remotely practical situation. In
+ // practice, we will have one dynamic table per HTTP/2 connection. If we
+ // assume a very powerful server that handles 1M QPS per connection and each
+ // request adds (then evicts) 100 entries from the table, it would still take
+ // 2M years for evictCount to overflow.
+ ents []HeaderField
+ evictCount uint64
+
+ // byName maps a HeaderField name to the unique id of the newest entry with
+ // the same name. See above for a definition of "unique id".
+ byName map[string]uint64
+
+ // byNameValue maps a HeaderField name/value pair to the unique id of the newest
+ // entry with the same name and value. See above for a definition of "unique id".
+ byNameValue map[pairNameValue]uint64
+}
+
+type pairNameValue struct {
+ name, value string
+}
+
+func (t *headerFieldTable) init() {
+ t.byName = make(map[string]uint64)
+ t.byNameValue = make(map[pairNameValue]uint64)
+}
+
+// len reports the number of entries in the table.
+func (t *headerFieldTable) len() int {
+ return len(t.ents)
+}
+
+// addEntry adds a new entry.
+func (t *headerFieldTable) addEntry(f HeaderField) {
+ id := uint64(t.len()) + t.evictCount + 1
+ t.byName[f.Name] = id
+ t.byNameValue[pairNameValue{f.Name, f.Value}] = id
+ t.ents = append(t.ents, f)
+}
+
+// evictOldest evicts the n oldest entries in the table.
+func (t *headerFieldTable) evictOldest(n int) {
+ if n > t.len() {
+ panic(fmt.Sprintf("evictOldest(%v) on table with %v entries", n, t.len()))
+ }
+ for k := 0; k < n; k++ {
+ f := t.ents[k]
+ id := t.evictCount + uint64(k) + 1
+ if t.byName[f.Name] == id {
+ t.byName[f.Name] = 0
+ }
+ if p := (pairNameValue{f.Name, f.Value}); t.byNameValue[p] == id {
+ t.byNameValue[p] = 0
+ }
+ }
+ copy(t.ents, t.ents[n:])
+ for k := t.len() - n; k < t.len(); k++ {
+ t.ents[k] = HeaderField{} // so strings can be garbage collected
+ }
+ t.ents = t.ents[:t.len()-n]
+ if t.evictCount+uint64(n) < t.evictCount {
+ panic("evictCount overflow")
+ }
+ t.evictCount += uint64(n)
+}
+
+// search finds f in the table. If there is no match, i is 0.
+// If both name and value match, i is the matched index and nameValueMatch
+// becomes true. If only name matches, i points to that index and
+// nameValueMatch becomes false.
+//
+// The returned index is a 1-based HPACK index. For dynamic tables, HPACK says
+// that index 1 should be the newest entry, but t.ents[0] is the oldest entry,
+// meaning t.ents is reversed for dynamic tables. Hence, when t is a dynamic
+// table, the return value i actually refers to the entry t.ents[t.len()-i].
+//
+// All tables are assumed to be a dynamic tables except for the global
+// staticTable pointer.
+//
+// See Section 2.3.3.
+func (t *headerFieldTable) search(f HeaderField) (i uint64, nameValueMatch bool) {
+ if !f.Sensitive {
+ if id := t.byNameValue[pairNameValue{f.Name, f.Value}]; id != 0 {
+ return t.idToIndex(id), true
+ }
+ }
+ if id := t.byName[f.Name]; id != 0 {
+ return t.idToIndex(id), false
+ }
+ return 0, false
+}
+
+// idToIndex converts a unique id to an HPACK index.
+// See Section 2.3.3.
+func (t *headerFieldTable) idToIndex(id uint64) uint64 {
+ if id <= t.evictCount {
+ panic(fmt.Sprintf("id (%v) <= evictCount (%v)", id, t.evictCount))
+ }
+ k := id - t.evictCount - 1 // convert id to an index t.ents[k]
+ if t != staticTable {
+ return uint64(t.len()) - k // dynamic table
+ }
+ return k + 1
+}
+
func pair(name, value string) HeaderField {
return HeaderField{Name: name, Value: value}
}
// http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-07#appendix-B
-var staticTable = [...]HeaderField{
- pair(":authority", ""), // index 1 (1-based)
- pair(":method", "GET"),
- pair(":method", "POST"),
- pair(":path", "/"),
- pair(":path", "/index.html"),
- pair(":scheme", "http"),
- pair(":scheme", "https"),
- pair(":status", "200"),
- pair(":status", "204"),
- pair(":status", "206"),
- pair(":status", "304"),
- pair(":status", "400"),
- pair(":status", "404"),
- pair(":status", "500"),
- pair("accept-charset", ""),
- pair("accept-encoding", "gzip, deflate"),
- pair("accept-language", ""),
- pair("accept-ranges", ""),
- pair("accept", ""),
- pair("access-control-allow-origin", ""),
- pair("age", ""),
- pair("allow", ""),
- pair("authorization", ""),
- pair("cache-control", ""),
- pair("content-disposition", ""),
- pair("content-encoding", ""),
- pair("content-language", ""),
- pair("content-length", ""),
- pair("content-location", ""),
- pair("content-range", ""),
- pair("content-type", ""),
- pair("cookie", ""),
- pair("date", ""),
- pair("etag", ""),
- pair("expect", ""),
- pair("expires", ""),
- pair("from", ""),
- pair("host", ""),
- pair("if-match", ""),
- pair("if-modified-since", ""),
- pair("if-none-match", ""),
- pair("if-range", ""),
- pair("if-unmodified-since", ""),
- pair("last-modified", ""),
- pair("link", ""),
- pair("location", ""),
- pair("max-forwards", ""),
- pair("proxy-authenticate", ""),
- pair("proxy-authorization", ""),
- pair("range", ""),
- pair("referer", ""),
- pair("refresh", ""),
- pair("retry-after", ""),
- pair("server", ""),
- pair("set-cookie", ""),
- pair("strict-transport-security", ""),
- pair("transfer-encoding", ""),
- pair("user-agent", ""),
- pair("vary", ""),
- pair("via", ""),
- pair("www-authenticate", ""),
+var staticTable = newStaticTable()
+
+func newStaticTable() *headerFieldTable {
+ t := &headerFieldTable{}
+ t.init()
+ t.addEntry(pair(":authority", ""))
+ t.addEntry(pair(":method", "GET"))
+ t.addEntry(pair(":method", "POST"))
+ t.addEntry(pair(":path", "/"))
+ t.addEntry(pair(":path", "/index.html"))
+ t.addEntry(pair(":scheme", "http"))
+ t.addEntry(pair(":scheme", "https"))
+ t.addEntry(pair(":status", "200"))
+ t.addEntry(pair(":status", "204"))
+ t.addEntry(pair(":status", "206"))
+ t.addEntry(pair(":status", "304"))
+ t.addEntry(pair(":status", "400"))
+ t.addEntry(pair(":status", "404"))
+ t.addEntry(pair(":status", "500"))
+ t.addEntry(pair("accept-charset", ""))
+ t.addEntry(pair("accept-encoding", "gzip, deflate"))
+ t.addEntry(pair("accept-language", ""))
+ t.addEntry(pair("accept-ranges", ""))
+ t.addEntry(pair("accept", ""))
+ t.addEntry(pair("access-control-allow-origin", ""))
+ t.addEntry(pair("age", ""))
+ t.addEntry(pair("allow", ""))
+ t.addEntry(pair("authorization", ""))
+ t.addEntry(pair("cache-control", ""))
+ t.addEntry(pair("content-disposition", ""))
+ t.addEntry(pair("content-encoding", ""))
+ t.addEntry(pair("content-language", ""))
+ t.addEntry(pair("content-length", ""))
+ t.addEntry(pair("content-location", ""))
+ t.addEntry(pair("content-range", ""))
+ t.addEntry(pair("content-type", ""))
+ t.addEntry(pair("cookie", ""))
+ t.addEntry(pair("date", ""))
+ t.addEntry(pair("etag", ""))
+ t.addEntry(pair("expect", ""))
+ t.addEntry(pair("expires", ""))
+ t.addEntry(pair("from", ""))
+ t.addEntry(pair("host", ""))
+ t.addEntry(pair("if-match", ""))
+ t.addEntry(pair("if-modified-since", ""))
+ t.addEntry(pair("if-none-match", ""))
+ t.addEntry(pair("if-range", ""))
+ t.addEntry(pair("if-unmodified-since", ""))
+ t.addEntry(pair("last-modified", ""))
+ t.addEntry(pair("link", ""))
+ t.addEntry(pair("location", ""))
+ t.addEntry(pair("max-forwards", ""))
+ t.addEntry(pair("proxy-authenticate", ""))
+ t.addEntry(pair("proxy-authorization", ""))
+ t.addEntry(pair("range", ""))
+ t.addEntry(pair("referer", ""))
+ t.addEntry(pair("refresh", ""))
+ t.addEntry(pair("retry-after", ""))
+ t.addEntry(pair("server", ""))
+ t.addEntry(pair("set-cookie", ""))
+ t.addEntry(pair("strict-transport-security", ""))
+ t.addEntry(pair("transfer-encoding", ""))
+ t.addEntry(pair("user-agent", ""))
+ t.addEntry(pair("vary", ""))
+ t.addEntry(pair("via", ""))
+ t.addEntry(pair("www-authenticate", ""))
+ return t
}
var huffmanCodes = [256]uint32{
diff --git a/http2/hpack/tables_test.go b/http2/hpack/tables_test.go
new file mode 100644
index 0000000..7f40d9a
--- /dev/null
+++ b/http2/hpack/tables_test.go
@@ -0,0 +1,188 @@
+// Copyright 2017 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package hpack
+
+import (
+ "bufio"
+ "regexp"
+ "strconv"
+ "strings"
+ "testing"
+)
+
+func TestHeaderFieldTable(t *testing.T) {
+ table := &headerFieldTable{}
+ table.init()
+ table.addEntry(pair("key1", "value1-1"))
+ table.addEntry(pair("key2", "value2-1"))
+ table.addEntry(pair("key1", "value1-2"))
+ table.addEntry(pair("key3", "value3-1"))
+ table.addEntry(pair("key4", "value4-1"))
+ table.addEntry(pair("key2", "value2-2"))
+
+ // Tests will be run twice: once before evicting anything, and
+ // again after evicting the three oldest entries.
+ tests := []struct {
+ f HeaderField
+ beforeWantStaticI uint64
+ beforeWantMatch bool
+ afterWantStaticI uint64
+ afterWantMatch bool
+ }{
+ {HeaderField{"key1", "value1-1", false}, 1, true, 0, false},
+ {HeaderField{"key1", "value1-2", false}, 3, true, 0, false},
+ {HeaderField{"key1", "value1-3", false}, 3, false, 0, false},
+ {HeaderField{"key2", "value2-1", false}, 2, true, 3, false},
+ {HeaderField{"key2", "value2-2", false}, 6, true, 3, true},
+ {HeaderField{"key2", "value2-3", false}, 6, false, 3, false},
+ {HeaderField{"key4", "value4-1", false}, 5, true, 2, true},
+ // Name match only, because sensitive.
+ {HeaderField{"key4", "value4-1", true}, 5, false, 2, false},
+ // Key not found.
+ {HeaderField{"key5", "value5-x", false}, 0, false, 0, false},
+ }
+
+ staticToDynamic := func(i uint64) uint64 {
+ if i == 0 {
+ return 0
+ }
+ return uint64(table.len()) - i + 1 // dynamic is the reversed table
+ }
+
+ searchStatic := func(f HeaderField) (uint64, bool) {
+ old := staticTable
+ staticTable = table
+ defer func() { staticTable = old }()
+ return staticTable.search(f)
+ }
+
+ searchDynamic := func(f HeaderField) (uint64, bool) {
+ return table.search(f)
+ }
+
+ for _, test := range tests {
+ gotI, gotMatch := searchStatic(test.f)
+ if wantI, wantMatch := test.beforeWantStaticI, test.beforeWantMatch; gotI != wantI || gotMatch != wantMatch {
+ t.Errorf("before evictions: searchStatic(%+v)=%v,%v want %v,%v", test.f, gotI, gotMatch, wantI, wantMatch)
+ }
+ gotI, gotMatch = searchDynamic(test.f)
+ wantDynamicI := staticToDynamic(test.beforeWantStaticI)
+ if wantI, wantMatch := wantDynamicI, test.beforeWantMatch; gotI != wantI || gotMatch != wantMatch {
+ t.Errorf("before evictions: searchDynamic(%+v)=%v,%v want %v,%v", test.f, gotI, gotMatch, wantI, wantMatch)
+ }
+ }
+
+ table.evictOldest(3)
+
+ for _, test := range tests {
+ gotI, gotMatch := searchStatic(test.f)
+ if wantI, wantMatch := test.afterWantStaticI, test.afterWantMatch; gotI != wantI || gotMatch != wantMatch {
+ t.Errorf("after evictions: searchStatic(%+v)=%v,%v want %v,%v", test.f, gotI, gotMatch, wantI, wantMatch)
+ }
+ gotI, gotMatch = searchDynamic(test.f)
+ wantDynamicI := staticToDynamic(test.afterWantStaticI)
+ if wantI, wantMatch := wantDynamicI, test.afterWantMatch; gotI != wantI || gotMatch != wantMatch {
+ t.Errorf("after evictions: searchDynamic(%+v)=%v,%v want %v,%v", test.f, gotI, gotMatch, wantI, wantMatch)
+ }
+ }
+}
+
+func TestStaticTable(t *testing.T) {
+ fromSpec := `
+ +-------+-----------------------------+---------------+
+ | 1 | :authority | |
+ | 2 | :method | GET |
+ | 3 | :method | POST |
+ | 4 | :path | / |
+ | 5 | :path | /index.html |
+ | 6 | :scheme | http |
+ | 7 | :scheme | https |
+ | 8 | :status | 200 |
+ | 9 | :status | 204 |
+ | 10 | :status | 206 |
+ | 11 | :status | 304 |
+ | 12 | :status | 400 |
+ | 13 | :status | 404 |
+ | 14 | :status | 500 |
+ | 15 | accept-charset | |
+ | 16 | accept-encoding | gzip, deflate |
+ | 17 | accept-language | |
+ | 18 | accept-ranges | |
+ | 19 | accept | |
+ | 20 | access-control-allow-origin | |
+ | 21 | age | |
+ | 22 | allow | |
+ | 23 | authorization | |
+ | 24 | cache-control | |
+ | 25 | content-disposition | |
+ | 26 | content-encoding | |
+ | 27 | content-language | |
+ | 28 | content-length | |
+ | 29 | content-location | |
+ | 30 | content-range | |
+ | 31 | content-type | |
+ | 32 | cookie | |
+ | 33 | date | |
+ | 34 | etag | |
+ | 35 | expect | |
+ | 36 | expires | |
+ | 37 | from | |
+ | 38 | host | |
+ | 39 | if-match | |
+ | 40 | if-modified-since | |
+ | 41 | if-none-match | |
+ | 42 | if-range | |
+ | 43 | if-unmodified-since | |
+ | 44 | last-modified | |
+ | 45 | link | |
+ | 46 | location | |
+ | 47 | max-forwards | |
+ | 48 | proxy-authenticate | |
+ | 49 | proxy-authorization | |
+ | 50 | range | |
+ | 51 | referer | |
+ | 52 | refresh | |
+ | 53 | retry-after | |
+ | 54 | server | |
+ | 55 | set-cookie | |
+ | 56 | strict-transport-security | |
+ | 57 | transfer-encoding | |
+ | 58 | user-agent | |
+ | 59 | vary | |
+ | 60 | via | |
+ | 61 | www-authenticate | |
+ +-------+-----------------------------+---------------+
+`
+ bs := bufio.NewScanner(strings.NewReader(fromSpec))
+ re := regexp.MustCompile(`\| (\d+)\s+\| (\S+)\s*\| (\S(.*\S)?)?\s+\|`)
+ for bs.Scan() {
+ l := bs.Text()
+ if !strings.Contains(l, "|") {
+ continue
+ }
+ m := re.FindStringSubmatch(l)
+ if m == nil {
+ continue
+ }
+ i, err := strconv.Atoi(m[1])
+ if err != nil {
+ t.Errorf("Bogus integer on line %q", l)
+ continue
+ }
+ if i < 1 || i > staticTable.len() {
+ t.Errorf("Bogus index %d on line %q", i, l)
+ continue
+ }
+ if got, want := staticTable.ents[i-1].Name, m[2]; got != want {
+ t.Errorf("header index %d name = %q; want %q", i, got, want)
+ }
+ if got, want := staticTable.ents[i-1].Value, m[3]; got != want {
+ t.Errorf("header index %d value = %q; want %q", i, got, want)
+ }
+ }
+ if err := bs.Err(); err != nil {
+ t.Error(err)
+ }
+}
