3 files changed, 220 insertions, 157 deletions

diff --git a/vendor/golang.org/x/net/http2/hpack/encode.go b/vendor/golang.org/x/net/http2/hpack/encode.go
index 6b3b9f8..54726c2 100644
--- a/vendor/golang.org/x/net/http2/hpack/encode.go
+++ b/vendor/golang.org/x/net/http2/hpack/encode.go
@@ -39,6 +39,7 @@ func NewEncoder(w io.Writer) *Encoder {
 		tableSizeUpdate: false,
 		w:               w,
 	}
+	e.dynTab.table.init()
 	e.dynTab.setMaxSize(initialHeaderTableSize)
 	return e
 }
@@ -88,29 +89,17 @@ func (e *Encoder) WriteField(f HeaderField) error {
 // 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 !constantTimeStringCompare(hf.Name, f.Name) {
-			continue
-		}
-		if i == 0 {
-			i = uint64(idx + 1)
-		}
-		if f.Sensitive {
-			continue
-		}
-		if !constantTimeStringCompare(hf.Value, f.Value) {
-			continue
-		}
-		i = uint64(idx + 1)
-		nameValueMatch = true
-		return
+	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/vendor/golang.org/x/net/http2/hpack/hpack.go b/vendor/golang.org/x/net/http2/hpack/hpack.go
index 007bc7f..176644a 100644
--- a/vendor/golang.org/x/net/http2/hpack/hpack.go
+++ b/vendor/golang.org/x/net/http2/hpack/hpack.go
@@ -102,6 +102,7 @@ func NewDecoder(maxDynamicTableSize uint32, emitFunc func(f HeaderField)) *Decod
 		emit:        emitFunc,
 		emitEnabled: true,
 	}
+	d.dynTab.table.init()
 	d.dynTab.allowedMaxSize = maxDynamicTableSize
 	d.dynTab.setMaxSize(maxDynamicTableSize)
 	return d
@@ -154,12 +155,9 @@ func (d *Decoder) SetAllowedMaxDynamicTableSize(v uint32) {
 }
 
 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,95 +167,45 @@ func (dt *dynamicTable) setMaxSize(v uint32) {
 	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:]
-	}
-
-	// Shift slice contents down if we evicted things.
-	if len(dt.ents) != len(base) {
-		copy(base, dt.ents)
-		dt.ents = base[:len(dt.ents)]
+	var n int
+	for dt.size > dt.maxSize && n < dt.table.len() {
+		dt.size -= dt.table.ents[n].Size()
+		n++
 	}
-}
-
-// constantTimeStringCompare compares string a and b in a constant
-// time manner.
-func constantTimeStringCompare(a, b string) bool {
-	if len(a) != len(b) {
-		return false
-	}
-
-	c := byte(0)
-
-	for i := 0; i < len(a); i++ {
-		c |= a[i] ^ b[i]
-	}
-
-	return c == 0
-}
-
-// 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 !constantTimeStringCompare(ent.Name, f.Name) {
-			continue
-		}
-		if i == 0 {
-			i = uint64(l - j)
-		}
-		if f.Sensitive {
-			continue
-		}
-		if !constantTimeStringCompare(ent.Value, f.Value) {
-			continue
-		}
-		i = uint64(l - j)
-		nameValueMatch = true
-		return
-	}
-	return
+	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/vendor/golang.org/x/net/http2/hpack/tables.go b/vendor/golang.org/x/net/http2/hpack/tables.go
index b9283a0..31bd5a5 100644
--- a/vendor/golang.org/x/net/http2/hpack/tables.go
+++ b/vendor/golang.org/x/net/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 {
+			delete(t.byName, f.Name)
+		}
+		if p := (pairNameValue{f.Name, f.Value}); t.byNameValue[p] == id {
+			delete(t.byNameValue, p)
+		}
+	}
+	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{