Skip to content

Commit 99c3b0a

Browse files
committed
http2/hpack: build the table lookup maps lazily, only for encoders
The headerFieldTable byName and byNameValue maps exist to serve search, which is only reachable from the Encoder. Decoder dynamic tables allocated and maintained them anyway, for every entry ever added or evicted, even though nothing ever read from them. For servers with many mostly-idle HTTP/2 connections, each pinning a decoder dynamic table for the connection's lifetime, those maps are a meaningful fraction of per-connection memory: on one proxy instance with ~124k long-poll connections, hpack table maps accounted for ~230MB of live heap. Build the maps lazily on the first search call instead, so decoders never allocate them. Encoder behavior is unchanged: its first WriteField builds the maps from the (usually empty) table and maintains them incrementally from then on, as before. Change-Id: I1db5d23c3ea8202497a559f70cdcd597f14fefa1 Reviewed-on: https://go-review.googlesource.com/c/net/+/807260 LUCI-TryBot-Result: [email protected] <[email protected]> Reviewed-by: Nicholas Husin <[email protected]> Reviewed-by: David Chase <[email protected]> Reviewed-by: Nicholas Husin <[email protected]>
1 parent 5a920b1 commit 99c3b0a

4 files changed

Lines changed: 78 additions & 18 deletions

File tree

‎http2/hpack/encode.go‎

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -39,7 +39,6 @@ func NewEncoder(w io.Writer) *Encoder {
3939
tableSizeUpdate: false,
4040
w: w,
4141
}
42-
e.dynTab.table.init()
4342
e.dynTab.setMaxSize(initialHeaderTableSize)
4443
return e
4544
}

‎http2/hpack/hpack.go‎

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -105,7 +105,6 @@ func NewDecoder(maxDynamicTableSize uint32, emitFunc func(f HeaderField)) *Decod
105105
emitEnabled: true,
106106
firstField: true,
107107
}
108-
d.dynTab.table.init()
109108
d.dynTab.allowedMaxSize = maxDynamicTableSize
110109
d.dynTab.setMaxSize(maxDynamicTableSize)
111110
return d

‎http2/hpack/tables.go‎

Lines changed: 37 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -31,20 +31,36 @@ type headerFieldTable struct {
3131

3232
// byName maps a HeaderField name to the unique id of the newest entry with
3333
// the same name. See above for a definition of "unique id".
34+
//
35+
// byName and byNameValue are used only by search, which is only called
36+
// for tables used by encoders. For tables used only by decoders, the
37+
// maps are never built, as a memory optimization for servers with many
38+
// mostly-idle connections, each pinning a dynamic table. The maps are
39+
// built lazily by the first search call and are nil until then. The two
40+
// maps are always both nil or both non-nil.
3441
byName map[string]uint64
3542

3643
// byNameValue maps a HeaderField name/value pair to the unique id of the newest
3744
// entry with the same name and value. See above for a definition of "unique id".
45+
// See byName for when this map is non-nil.
3846
byNameValue map[pairNameValue]uint64
3947
}
4048

4149
type pairNameValue struct {
4250
name, value string
4351
}
4452

45-
func (t *headerFieldTable) init() {
46-
t.byName = make(map[string]uint64)
47-
t.byNameValue = make(map[pairNameValue]uint64)
53+
// buildMaps initializes byName and byNameValue from ents.
54+
func (t *headerFieldTable) buildMaps() {
55+
t.byName = make(map[string]uint64, len(t.ents))
56+
t.byNameValue = make(map[pairNameValue]uint64, len(t.ents))
57+
for k, f := range t.ents {
58+
// Map to the newest matching entry: later (newer) entries
59+
// overwrite earlier ones, matching addEntry's behavior.
60+
id := t.evictCount + uint64(k) + 1
61+
t.byName[f.Name] = id
62+
t.byNameValue[pairNameValue{f.Name, f.Value}] = id
63+
}
4864
}
4965

5066
// len reports the number of entries in the table.
@@ -54,9 +70,11 @@ func (t *headerFieldTable) len() int {
5470

5571
// addEntry adds a new entry.
5672
func (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
73+
if t.byName != nil {
74+
id := uint64(t.len()) + t.evictCount + 1
75+
t.byName[f.Name] = id
76+
t.byNameValue[pairNameValue{f.Name, f.Value}] = id
77+
}
6078
t.ents = append(t.ents, f)
6179
}
6280

@@ -65,14 +83,16 @@ func (t *headerFieldTable) evictOldest(n int) {
6583
if n > t.len() {
6684
panic(fmt.Sprintf("evictOldest(%v) on table with %v entries", n, t.len()))
6785
}
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)
86+
if t.byName != nil {
87+
for k := 0; k < n; k++ {
88+
f := t.ents[k]
89+
id := t.evictCount + uint64(k) + 1
90+
if t.byName[f.Name] == id {
91+
delete(t.byName, f.Name)
92+
}
93+
if p := (pairNameValue{f.Name, f.Value}); t.byNameValue[p] == id {
94+
delete(t.byNameValue, p)
95+
}
7696
}
7797
}
7898
copy(t.ents, t.ents[n:])
@@ -100,6 +120,9 @@ func (t *headerFieldTable) evictOldest(n int) {
100120
//
101121
// See Section 2.3.3.
102122
func (t *headerFieldTable) search(f HeaderField) (i uint64, nameValueMatch bool) {
123+
if t.byName == nil {
124+
t.buildMaps()
125+
}
103126
if !f.Sensitive {
104127
if id := t.byNameValue[pairNameValue{f.Name, f.Value}]; id != 0 {
105128
return t.idToIndex(id), true

‎http2/hpack/tables_test.go‎

Lines changed: 41 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -14,7 +14,6 @@ import (
1414

1515
func TestHeaderFieldTable(t *testing.T) {
1616
table := &headerFieldTable{}
17-
table.init()
1817
table.addEntry(pair("key1", "value1-1"))
1918
table.addEntry(pair("key2", "value2-1"))
2019
table.addEntry(pair("key1", "value1-2"))
@@ -91,14 +90,16 @@ func TestHeaderFieldTable(t *testing.T) {
9190

9291
func TestHeaderFieldTable_LookupMapEviction(t *testing.T) {
9392
table := &headerFieldTable{}
94-
table.init()
9593
table.addEntry(pair("key1", "value1-1"))
9694
table.addEntry(pair("key2", "value2-1"))
9795
table.addEntry(pair("key1", "value1-2"))
9896
table.addEntry(pair("key3", "value3-1"))
9997
table.addEntry(pair("key4", "value4-1"))
10098
table.addEntry(pair("key2", "value2-2"))
10199

100+
// Build the lookup maps so eviction has maps to maintain.
101+
table.search(pair("key1", "value1-1"))
102+
102103
// evict all pairs
103104
table.evictOldest(table.len())
104105

@@ -115,6 +116,44 @@ func TestHeaderFieldTable_LookupMapEviction(t *testing.T) {
115116
}
116117
}
117118

119+
// TestHeaderFieldTable_MapsBuiltLazily verifies that a table used without
120+
// search (as by decoders) never allocates its lookup maps, and that maps
121+
// built after evictions reflect only the surviving entries.
122+
func TestHeaderFieldTable_MapsBuiltLazily(t *testing.T) {
123+
table := &headerFieldTable{}
124+
table.addEntry(pair("key1", "value1-1"))
125+
table.addEntry(pair("key2", "value2-1"))
126+
table.addEntry(pair("key1", "value1-2"))
127+
table.evictOldest(1)
128+
129+
if table.byName != nil || table.byNameValue != nil {
130+
t.Fatalf("lookup maps allocated without search")
131+
}
132+
133+
// The first search builds the maps from the surviving entries.
134+
if i, match := table.search(pair("key1", "value1-2")); i != 1 || !match {
135+
t.Errorf("search(key1, value1-2) = %v, %v; want 1, true", i, match)
136+
}
137+
if i, match := table.search(pair("key2", "wrong-value")); i != 2 || match {
138+
t.Errorf("search(key2, wrong-value) = %v, %v; want 2, false", i, match)
139+
}
140+
if _, ok := table.byName["key1"]; !ok {
141+
t.Errorf("byName missing key1")
142+
}
143+
if got, want := len(table.byName), 2; got != want {
144+
t.Errorf("len(byName) = %d, want %d", got, want)
145+
}
146+
if got, want := len(table.byNameValue), 2; got != want {
147+
t.Errorf("len(byNameValue) = %d, want %d", got, want)
148+
}
149+
150+
// Entries added after the maps exist keep them up to date.
151+
table.addEntry(pair("key3", "value3-1"))
152+
if i, match := table.search(pair("key3", "value3-1")); i != 1 || !match {
153+
t.Errorf("search(key3, value3-1) = %v, %v; want 1, true", i, match)
154+
}
155+
}
156+
118157
func TestStaticTable(t *testing.T) {
119158
fromSpec := `
120159
+-------+-----------------------------+---------------+

0 commit comments

Comments
 (0)