Project import generated by Copybara. PiperOrigin-RevId: 229942388 Change-Id: Ib5a23c152c95ed4294cece9f902227c21ce531ef
diff --git a/spdy/core/hpack/hpack_constants.cc b/spdy/core/hpack/hpack_constants.cc new file mode 100644 index 0000000..9c1498a --- /dev/null +++ b/spdy/core/hpack/hpack_constants.cc
@@ -0,0 +1,386 @@ +// Copyright 2014 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_constants.h" + +#include <cstddef> +#include <memory> +#include <vector> + +#include "base/logging.h" +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_huffman_table.h" +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_static_table.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_arraysize.h" + +namespace spdy { + +// Produced by applying the python program [1] with tables provided by [2] +// (inserted into the source of the python program) and copy-paste them into +// this file. +// +// [1] net/tools/build_hpack_constants.py in Chromium +// [2] http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-08 + +// HpackHuffmanSymbol entries are initialized as {code, length, id}. +// Codes are specified in the |length| most-significant bits of |code|. +const std::vector<HpackHuffmanSymbol>& HpackHuffmanCodeVector() { + static const auto* kHpackHuffmanCode = new std::vector<HpackHuffmanSymbol>{ + {0xffc00000ul, 13, 0}, // 11111111|11000 + {0xffffb000ul, 23, 1}, // 11111111|11111111|1011000 + {0xfffffe20ul, 28, 2}, // 11111111|11111111|11111110|0010 + {0xfffffe30ul, 28, 3}, // 11111111|11111111|11111110|0011 + {0xfffffe40ul, 28, 4}, // 11111111|11111111|11111110|0100 + {0xfffffe50ul, 28, 5}, // 11111111|11111111|11111110|0101 + {0xfffffe60ul, 28, 6}, // 11111111|11111111|11111110|0110 + {0xfffffe70ul, 28, 7}, // 11111111|11111111|11111110|0111 + {0xfffffe80ul, 28, 8}, // 11111111|11111111|11111110|1000 + {0xffffea00ul, 24, 9}, // 11111111|11111111|11101010 + {0xfffffff0ul, 30, 10}, // 11111111|11111111|11111111|111100 + {0xfffffe90ul, 28, 11}, // 11111111|11111111|11111110|1001 + {0xfffffea0ul, 28, 12}, // 11111111|11111111|11111110|1010 + {0xfffffff4ul, 30, 13}, // 11111111|11111111|11111111|111101 + {0xfffffeb0ul, 28, 14}, // 11111111|11111111|11111110|1011 + {0xfffffec0ul, 28, 15}, // 11111111|11111111|11111110|1100 + {0xfffffed0ul, 28, 16}, // 11111111|11111111|11111110|1101 + {0xfffffee0ul, 28, 17}, // 11111111|11111111|11111110|1110 + {0xfffffef0ul, 28, 18}, // 11111111|11111111|11111110|1111 + {0xffffff00ul, 28, 19}, // 11111111|11111111|11111111|0000 + {0xffffff10ul, 28, 20}, // 11111111|11111111|11111111|0001 + {0xffffff20ul, 28, 21}, // 11111111|11111111|11111111|0010 + {0xfffffff8ul, 30, 22}, // 11111111|11111111|11111111|111110 + {0xffffff30ul, 28, 23}, // 11111111|11111111|11111111|0011 + {0xffffff40ul, 28, 24}, // 11111111|11111111|11111111|0100 + {0xffffff50ul, 28, 25}, // 11111111|11111111|11111111|0101 + {0xffffff60ul, 28, 26}, // 11111111|11111111|11111111|0110 + {0xffffff70ul, 28, 27}, // 11111111|11111111|11111111|0111 + {0xffffff80ul, 28, 28}, // 11111111|11111111|11111111|1000 + {0xffffff90ul, 28, 29}, // 11111111|11111111|11111111|1001 + {0xffffffa0ul, 28, 30}, // 11111111|11111111|11111111|1010 + {0xffffffb0ul, 28, 31}, // 11111111|11111111|11111111|1011 + {0x50000000ul, 6, 32}, // ' ' 010100 + {0xfe000000ul, 10, 33}, // '!' 11111110|00 + {0xfe400000ul, 10, 34}, // '"' 11111110|01 + {0xffa00000ul, 12, 35}, // '#' 11111111|1010 + {0xffc80000ul, 13, 36}, // '$' 11111111|11001 + {0x54000000ul, 6, 37}, // '%' 010101 + {0xf8000000ul, 8, 38}, // '&' 11111000 + {0xff400000ul, 11, 39}, // ''' 11111111|010 + {0xfe800000ul, 10, 40}, // '(' 11111110|10 + {0xfec00000ul, 10, 41}, // ')' 11111110|11 + {0xf9000000ul, 8, 42}, // '*' 11111001 + {0xff600000ul, 11, 43}, // '+' 11111111|011 + {0xfa000000ul, 8, 44}, // ',' 11111010 + {0x58000000ul, 6, 45}, // '-' 010110 + {0x5c000000ul, 6, 46}, // '.' 010111 + {0x60000000ul, 6, 47}, // '/' 011000 + {0x00000000ul, 5, 48}, // '0' 00000 + {0x08000000ul, 5, 49}, // '1' 00001 + {0x10000000ul, 5, 50}, // '2' 00010 + {0x64000000ul, 6, 51}, // '3' 011001 + {0x68000000ul, 6, 52}, // '4' 011010 + {0x6c000000ul, 6, 53}, // '5' 011011 + {0x70000000ul, 6, 54}, // '6' 011100 + {0x74000000ul, 6, 55}, // '7' 011101 + {0x78000000ul, 6, 56}, // '8' 011110 + {0x7c000000ul, 6, 57}, // '9' 011111 + {0xb8000000ul, 7, 58}, // ':' 1011100 + {0xfb000000ul, 8, 59}, // ';' 11111011 + {0xfff80000ul, 15, 60}, // '<' 11111111|1111100 + {0x80000000ul, 6, 61}, // '=' 100000 + {0xffb00000ul, 12, 62}, // '>' 11111111|1011 + {0xff000000ul, 10, 63}, // '?' 11111111|00 + {0xffd00000ul, 13, 64}, // '@' 11111111|11010 + {0x84000000ul, 6, 65}, // 'A' 100001 + {0xba000000ul, 7, 66}, // 'B' 1011101 + {0xbc000000ul, 7, 67}, // 'C' 1011110 + {0xbe000000ul, 7, 68}, // 'D' 1011111 + {0xc0000000ul, 7, 69}, // 'E' 1100000 + {0xc2000000ul, 7, 70}, // 'F' 1100001 + {0xc4000000ul, 7, 71}, // 'G' 1100010 + {0xc6000000ul, 7, 72}, // 'H' 1100011 + {0xc8000000ul, 7, 73}, // 'I' 1100100 + {0xca000000ul, 7, 74}, // 'J' 1100101 + {0xcc000000ul, 7, 75}, // 'K' 1100110 + {0xce000000ul, 7, 76}, // 'L' 1100111 + {0xd0000000ul, 7, 77}, // 'M' 1101000 + {0xd2000000ul, 7, 78}, // 'N' 1101001 + {0xd4000000ul, 7, 79}, // 'O' 1101010 + {0xd6000000ul, 7, 80}, // 'P' 1101011 + {0xd8000000ul, 7, 81}, // 'Q' 1101100 + {0xda000000ul, 7, 82}, // 'R' 1101101 + {0xdc000000ul, 7, 83}, // 'S' 1101110 + {0xde000000ul, 7, 84}, // 'T' 1101111 + {0xe0000000ul, 7, 85}, // 'U' 1110000 + {0xe2000000ul, 7, 86}, // 'V' 1110001 + {0xe4000000ul, 7, 87}, // 'W' 1110010 + {0xfc000000ul, 8, 88}, // 'X' 11111100 + {0xe6000000ul, 7, 89}, // 'Y' 1110011 + {0xfd000000ul, 8, 90}, // 'Z' 11111101 + {0xffd80000ul, 13, 91}, // '[' 11111111|11011 + {0xfffe0000ul, 19, 92}, // '\' 11111111|11111110|000 + {0xffe00000ul, 13, 93}, // ']' 11111111|11100 + {0xfff00000ul, 14, 94}, // '^' 11111111|111100 + {0x88000000ul, 6, 95}, // '_' 100010 + {0xfffa0000ul, 15, 96}, // '`' 11111111|1111101 + {0x18000000ul, 5, 97}, // 'a' 00011 + {0x8c000000ul, 6, 98}, // 'b' 100011 + {0x20000000ul, 5, 99}, // 'c' 00100 + {0x90000000ul, 6, 100}, // 'd' 100100 + {0x28000000ul, 5, 101}, // 'e' 00101 + {0x94000000ul, 6, 102}, // 'f' 100101 + {0x98000000ul, 6, 103}, // 'g' 100110 + {0x9c000000ul, 6, 104}, // 'h' 100111 + {0x30000000ul, 5, 105}, // 'i' 00110 + {0xe8000000ul, 7, 106}, // 'j' 1110100 + {0xea000000ul, 7, 107}, // 'k' 1110101 + {0xa0000000ul, 6, 108}, // 'l' 101000 + {0xa4000000ul, 6, 109}, // 'm' 101001 + {0xa8000000ul, 6, 110}, // 'n' 101010 + {0x38000000ul, 5, 111}, // 'o' 00111 + {0xac000000ul, 6, 112}, // 'p' 101011 + {0xec000000ul, 7, 113}, // 'q' 1110110 + {0xb0000000ul, 6, 114}, // 'r' 101100 + {0x40000000ul, 5, 115}, // 's' 01000 + {0x48000000ul, 5, 116}, // 't' 01001 + {0xb4000000ul, 6, 117}, // 'u' 101101 + {0xee000000ul, 7, 118}, // 'v' 1110111 + {0xf0000000ul, 7, 119}, // 'w' 1111000 + {0xf2000000ul, 7, 120}, // 'x' 1111001 + {0xf4000000ul, 7, 121}, // 'y' 1111010 + {0xf6000000ul, 7, 122}, // 'z' 1111011 + {0xfffc0000ul, 15, 123}, // '{' 11111111|1111110 + {0xff800000ul, 11, 124}, // '|' 11111111|100 + {0xfff40000ul, 14, 125}, // '}' 11111111|111101 + {0xffe80000ul, 13, 126}, // '~' 11111111|11101 + {0xffffffc0ul, 28, 127}, // 11111111|11111111|11111111|1100 + {0xfffe6000ul, 20, 128}, // 11111111|11111110|0110 + {0xffff4800ul, 22, 129}, // 11111111|11111111|010010 + {0xfffe7000ul, 20, 130}, // 11111111|11111110|0111 + {0xfffe8000ul, 20, 131}, // 11111111|11111110|1000 + {0xffff4c00ul, 22, 132}, // 11111111|11111111|010011 + {0xffff5000ul, 22, 133}, // 11111111|11111111|010100 + {0xffff5400ul, 22, 134}, // 11111111|11111111|010101 + {0xffffb200ul, 23, 135}, // 11111111|11111111|1011001 + {0xffff5800ul, 22, 136}, // 11111111|11111111|010110 + {0xffffb400ul, 23, 137}, // 11111111|11111111|1011010 + {0xffffb600ul, 23, 138}, // 11111111|11111111|1011011 + {0xffffb800ul, 23, 139}, // 11111111|11111111|1011100 + {0xffffba00ul, 23, 140}, // 11111111|11111111|1011101 + {0xffffbc00ul, 23, 141}, // 11111111|11111111|1011110 + {0xffffeb00ul, 24, 142}, // 11111111|11111111|11101011 + {0xffffbe00ul, 23, 143}, // 11111111|11111111|1011111 + {0xffffec00ul, 24, 144}, // 11111111|11111111|11101100 + {0xffffed00ul, 24, 145}, // 11111111|11111111|11101101 + {0xffff5c00ul, 22, 146}, // 11111111|11111111|010111 + {0xffffc000ul, 23, 147}, // 11111111|11111111|1100000 + {0xffffee00ul, 24, 148}, // 11111111|11111111|11101110 + {0xffffc200ul, 23, 149}, // 11111111|11111111|1100001 + {0xffffc400ul, 23, 150}, // 11111111|11111111|1100010 + {0xffffc600ul, 23, 151}, // 11111111|11111111|1100011 + {0xffffc800ul, 23, 152}, // 11111111|11111111|1100100 + {0xfffee000ul, 21, 153}, // 11111111|11111110|11100 + {0xffff6000ul, 22, 154}, // 11111111|11111111|011000 + {0xffffca00ul, 23, 155}, // 11111111|11111111|1100101 + {0xffff6400ul, 22, 156}, // 11111111|11111111|011001 + {0xffffcc00ul, 23, 157}, // 11111111|11111111|1100110 + {0xffffce00ul, 23, 158}, // 11111111|11111111|1100111 + {0xffffef00ul, 24, 159}, // 11111111|11111111|11101111 + {0xffff6800ul, 22, 160}, // 11111111|11111111|011010 + {0xfffee800ul, 21, 161}, // 11111111|11111110|11101 + {0xfffe9000ul, 20, 162}, // 11111111|11111110|1001 + {0xffff6c00ul, 22, 163}, // 11111111|11111111|011011 + {0xffff7000ul, 22, 164}, // 11111111|11111111|011100 + {0xffffd000ul, 23, 165}, // 11111111|11111111|1101000 + {0xffffd200ul, 23, 166}, // 11111111|11111111|1101001 + {0xfffef000ul, 21, 167}, // 11111111|11111110|11110 + {0xffffd400ul, 23, 168}, // 11111111|11111111|1101010 + {0xffff7400ul, 22, 169}, // 11111111|11111111|011101 + {0xffff7800ul, 22, 170}, // 11111111|11111111|011110 + {0xfffff000ul, 24, 171}, // 11111111|11111111|11110000 + {0xfffef800ul, 21, 172}, // 11111111|11111110|11111 + {0xffff7c00ul, 22, 173}, // 11111111|11111111|011111 + {0xffffd600ul, 23, 174}, // 11111111|11111111|1101011 + {0xffffd800ul, 23, 175}, // 11111111|11111111|1101100 + {0xffff0000ul, 21, 176}, // 11111111|11111111|00000 + {0xffff0800ul, 21, 177}, // 11111111|11111111|00001 + {0xffff8000ul, 22, 178}, // 11111111|11111111|100000 + {0xffff1000ul, 21, 179}, // 11111111|11111111|00010 + {0xffffda00ul, 23, 180}, // 11111111|11111111|1101101 + {0xffff8400ul, 22, 181}, // 11111111|11111111|100001 + {0xffffdc00ul, 23, 182}, // 11111111|11111111|1101110 + {0xffffde00ul, 23, 183}, // 11111111|11111111|1101111 + {0xfffea000ul, 20, 184}, // 11111111|11111110|1010 + {0xffff8800ul, 22, 185}, // 11111111|11111111|100010 + {0xffff8c00ul, 22, 186}, // 11111111|11111111|100011 + {0xffff9000ul, 22, 187}, // 11111111|11111111|100100 + {0xffffe000ul, 23, 188}, // 11111111|11111111|1110000 + {0xffff9400ul, 22, 189}, // 11111111|11111111|100101 + {0xffff9800ul, 22, 190}, // 11111111|11111111|100110 + {0xffffe200ul, 23, 191}, // 11111111|11111111|1110001 + {0xfffff800ul, 26, 192}, // 11111111|11111111|11111000|00 + {0xfffff840ul, 26, 193}, // 11111111|11111111|11111000|01 + {0xfffeb000ul, 20, 194}, // 11111111|11111110|1011 + {0xfffe2000ul, 19, 195}, // 11111111|11111110|001 + {0xffff9c00ul, 22, 196}, // 11111111|11111111|100111 + {0xffffe400ul, 23, 197}, // 11111111|11111111|1110010 + {0xffffa000ul, 22, 198}, // 11111111|11111111|101000 + {0xfffff600ul, 25, 199}, // 11111111|11111111|11110110|0 + {0xfffff880ul, 26, 200}, // 11111111|11111111|11111000|10 + {0xfffff8c0ul, 26, 201}, // 11111111|11111111|11111000|11 + {0xfffff900ul, 26, 202}, // 11111111|11111111|11111001|00 + {0xfffffbc0ul, 27, 203}, // 11111111|11111111|11111011|110 + {0xfffffbe0ul, 27, 204}, // 11111111|11111111|11111011|111 + {0xfffff940ul, 26, 205}, // 11111111|11111111|11111001|01 + {0xfffff100ul, 24, 206}, // 11111111|11111111|11110001 + {0xfffff680ul, 25, 207}, // 11111111|11111111|11110110|1 + {0xfffe4000ul, 19, 208}, // 11111111|11111110|010 + {0xffff1800ul, 21, 209}, // 11111111|11111111|00011 + {0xfffff980ul, 26, 210}, // 11111111|11111111|11111001|10 + {0xfffffc00ul, 27, 211}, // 11111111|11111111|11111100|000 + {0xfffffc20ul, 27, 212}, // 11111111|11111111|11111100|001 + {0xfffff9c0ul, 26, 213}, // 11111111|11111111|11111001|11 + {0xfffffc40ul, 27, 214}, // 11111111|11111111|11111100|010 + {0xfffff200ul, 24, 215}, // 11111111|11111111|11110010 + {0xffff2000ul, 21, 216}, // 11111111|11111111|00100 + {0xffff2800ul, 21, 217}, // 11111111|11111111|00101 + {0xfffffa00ul, 26, 218}, // 11111111|11111111|11111010|00 + {0xfffffa40ul, 26, 219}, // 11111111|11111111|11111010|01 + {0xffffffd0ul, 28, 220}, // 11111111|11111111|11111111|1101 + {0xfffffc60ul, 27, 221}, // 11111111|11111111|11111100|011 + {0xfffffc80ul, 27, 222}, // 11111111|11111111|11111100|100 + {0xfffffca0ul, 27, 223}, // 11111111|11111111|11111100|101 + {0xfffec000ul, 20, 224}, // 11111111|11111110|1100 + {0xfffff300ul, 24, 225}, // 11111111|11111111|11110011 + {0xfffed000ul, 20, 226}, // 11111111|11111110|1101 + {0xffff3000ul, 21, 227}, // 11111111|11111111|00110 + {0xffffa400ul, 22, 228}, // 11111111|11111111|101001 + {0xffff3800ul, 21, 229}, // 11111111|11111111|00111 + {0xffff4000ul, 21, 230}, // 11111111|11111111|01000 + {0xffffe600ul, 23, 231}, // 11111111|11111111|1110011 + {0xffffa800ul, 22, 232}, // 11111111|11111111|101010 + {0xffffac00ul, 22, 233}, // 11111111|11111111|101011 + {0xfffff700ul, 25, 234}, // 11111111|11111111|11110111|0 + {0xfffff780ul, 25, 235}, // 11111111|11111111|11110111|1 + {0xfffff400ul, 24, 236}, // 11111111|11111111|11110100 + {0xfffff500ul, 24, 237}, // 11111111|11111111|11110101 + {0xfffffa80ul, 26, 238}, // 11111111|11111111|11111010|10 + {0xffffe800ul, 23, 239}, // 11111111|11111111|1110100 + {0xfffffac0ul, 26, 240}, // 11111111|11111111|11111010|11 + {0xfffffcc0ul, 27, 241}, // 11111111|11111111|11111100|110 + {0xfffffb00ul, 26, 242}, // 11111111|11111111|11111011|00 + {0xfffffb40ul, 26, 243}, // 11111111|11111111|11111011|01 + {0xfffffce0ul, 27, 244}, // 11111111|11111111|11111100|111 + {0xfffffd00ul, 27, 245}, // 11111111|11111111|11111101|000 + {0xfffffd20ul, 27, 246}, // 11111111|11111111|11111101|001 + {0xfffffd40ul, 27, 247}, // 11111111|11111111|11111101|010 + {0xfffffd60ul, 27, 248}, // 11111111|11111111|11111101|011 + {0xffffffe0ul, 28, 249}, // 11111111|11111111|11111111|1110 + {0xfffffd80ul, 27, 250}, // 11111111|11111111|11111101|100 + {0xfffffda0ul, 27, 251}, // 11111111|11111111|11111101|101 + {0xfffffdc0ul, 27, 252}, // 11111111|11111111|11111101|110 + {0xfffffde0ul, 27, 253}, // 11111111|11111111|11111101|111 + {0xfffffe00ul, 27, 254}, // 11111111|11111111|11111110|000 + {0xfffffb80ul, 26, 255}, // 11111111|11111111|11111011|10 + {0xfffffffcul, 30, 256}, // EOS 11111111|11111111|11111111|111111 + }; + return *kHpackHuffmanCode; +} + +// The "constructor" for a HpackStaticEntry that computes the lengths at +// compile time. +#define STATIC_ENTRY(name, value) \ + { name, SPDY_ARRAYSIZE(name) - 1, value, SPDY_ARRAYSIZE(value) - 1 } + +const std::vector<HpackStaticEntry>& HpackStaticTableVector() { + static const auto* kHpackStaticTable = new std::vector<HpackStaticEntry>{ + STATIC_ENTRY(":authority", ""), // 1 + STATIC_ENTRY(":method", "GET"), // 2 + STATIC_ENTRY(":method", "POST"), // 3 + STATIC_ENTRY(":path", "/"), // 4 + STATIC_ENTRY(":path", "/index.html"), // 5 + STATIC_ENTRY(":scheme", "http"), // 6 + STATIC_ENTRY(":scheme", "https"), // 7 + STATIC_ENTRY(":status", "200"), // 8 + STATIC_ENTRY(":status", "204"), // 9 + STATIC_ENTRY(":status", "206"), // 10 + STATIC_ENTRY(":status", "304"), // 11 + STATIC_ENTRY(":status", "400"), // 12 + STATIC_ENTRY(":status", "404"), // 13 + STATIC_ENTRY(":status", "500"), // 14 + STATIC_ENTRY("accept-charset", ""), // 15 + STATIC_ENTRY("accept-encoding", "gzip, deflate"), // 16 + STATIC_ENTRY("accept-language", ""), // 17 + STATIC_ENTRY("accept-ranges", ""), // 18 + STATIC_ENTRY("accept", ""), // 19 + STATIC_ENTRY("access-control-allow-origin", ""), // 20 + STATIC_ENTRY("age", ""), // 21 + STATIC_ENTRY("allow", ""), // 22 + STATIC_ENTRY("authorization", ""), // 23 + STATIC_ENTRY("cache-control", ""), // 24 + STATIC_ENTRY("content-disposition", ""), // 25 + STATIC_ENTRY("content-encoding", ""), // 26 + STATIC_ENTRY("content-language", ""), // 27 + STATIC_ENTRY("content-length", ""), // 28 + STATIC_ENTRY("content-location", ""), // 29 + STATIC_ENTRY("content-range", ""), // 30 + STATIC_ENTRY("content-type", ""), // 31 + STATIC_ENTRY("cookie", ""), // 32 + STATIC_ENTRY("date", ""), // 33 + STATIC_ENTRY("etag", ""), // 34 + STATIC_ENTRY("expect", ""), // 35 + STATIC_ENTRY("expires", ""), // 36 + STATIC_ENTRY("from", ""), // 37 + STATIC_ENTRY("host", ""), // 38 + STATIC_ENTRY("if-match", ""), // 39 + STATIC_ENTRY("if-modified-since", ""), // 40 + STATIC_ENTRY("if-none-match", ""), // 41 + STATIC_ENTRY("if-range", ""), // 42 + STATIC_ENTRY("if-unmodified-since", ""), // 43 + STATIC_ENTRY("last-modified", ""), // 44 + STATIC_ENTRY("link", ""), // 45 + STATIC_ENTRY("location", ""), // 46 + STATIC_ENTRY("max-forwards", ""), // 47 + STATIC_ENTRY("proxy-authenticate", ""), // 48 + STATIC_ENTRY("proxy-authorization", ""), // 49 + STATIC_ENTRY("range", ""), // 50 + STATIC_ENTRY("referer", ""), // 51 + STATIC_ENTRY("refresh", ""), // 52 + STATIC_ENTRY("retry-after", ""), // 53 + STATIC_ENTRY("server", ""), // 54 + STATIC_ENTRY("set-cookie", ""), // 55 + STATIC_ENTRY("strict-transport-security", ""), // 56 + STATIC_ENTRY("transfer-encoding", ""), // 57 + STATIC_ENTRY("user-agent", ""), // 58 + STATIC_ENTRY("vary", ""), // 59 + STATIC_ENTRY("via", ""), // 60 + STATIC_ENTRY("www-authenticate", ""), // 61 + }; + return *kHpackStaticTable; +} + +#undef STATIC_ENTRY + +const HpackHuffmanTable& ObtainHpackHuffmanTable() { + static const HpackHuffmanTable* const shared_huffman_table = []() { + auto* table = new HpackHuffmanTable(); + CHECK(table->Initialize(HpackHuffmanCodeVector().data(), + HpackHuffmanCodeVector().size())); + CHECK(table->IsInitialized()); + return table; + }(); + return *shared_huffman_table; +} + +const HpackStaticTable& ObtainHpackStaticTable() { + static const HpackStaticTable* const shared_static_table = []() { + auto* table = new HpackStaticTable(); + table->Initialize(HpackStaticTableVector().data(), + HpackStaticTableVector().size()); + CHECK(table->IsInitialized()); + return table; + }(); + return *shared_static_table; +} + +} // namespace spdy
diff --git a/spdy/core/hpack/hpack_constants.h b/spdy/core/hpack/hpack_constants.h new file mode 100644 index 0000000..3f4026b --- /dev/null +++ b/spdy/core/hpack/hpack_constants.h
@@ -0,0 +1,95 @@ +// Copyright 2014 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#ifndef QUICHE_SPDY_CORE_HPACK_HPACK_CONSTANTS_H_ +#define QUICHE_SPDY_CORE_HPACK_HPACK_CONSTANTS_H_ + +#include <cstddef> +#include <cstdint> +#include <vector> + +#include "net/third_party/quiche/src/spdy/platform/api/spdy_export.h" + +// All section references below are to +// http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-08 + +namespace spdy { + +// An HpackPrefix signifies |bits| stored in the top |bit_size| bits +// of an octet. +struct HpackPrefix { + uint8_t bits; + size_t bit_size; +}; + +// Represents a symbol and its Huffman code (stored in most-significant bits). +struct HpackHuffmanSymbol { + uint32_t code; + uint8_t length; + uint16_t id; +}; + +// An entry in the static table. Must be a POD in order to avoid static +// initializers, i.e. no user-defined constructors or destructors. +struct HpackStaticEntry { + const char* const name; + const size_t name_len; + const char* const value; + const size_t value_len; +}; + +class HpackHuffmanTable; +class HpackStaticTable; + +// Defined in RFC 7540, 6.5.2. +const uint32_t kDefaultHeaderTableSizeSetting = 4096; + +// RFC 7541, 5.2: Flag for a string literal that is stored unmodified (i.e., +// without Huffman encoding). +const HpackPrefix kStringLiteralIdentityEncoded = {0x0, 1}; + +// RFC 7541, 5.2: Flag for a Huffman-coded string literal. +const HpackPrefix kStringLiteralHuffmanEncoded = {0x1, 1}; + +// RFC 7541, 6.1: Opcode for an indexed header field. +const HpackPrefix kIndexedOpcode = {0b1, 1}; + +// RFC 7541, 6.2.1: Opcode for a literal header field with incremental indexing. +const HpackPrefix kLiteralIncrementalIndexOpcode = {0b01, 2}; + +// RFC 7541, 6.2.2: Opcode for a literal header field without indexing. +const HpackPrefix kLiteralNoIndexOpcode = {0b0000, 4}; + +// RFC 7541, 6.2.3: Opcode for a literal header field which is never indexed. +// Currently unused. +// const HpackPrefix kLiteralNeverIndexOpcode = {0b0001, 4}; + +// RFC 7541, 6.3: Opcode for maximum header table size update. Begins a +// varint-encoded table size with a 5-bit prefix. +const HpackPrefix kHeaderTableSizeUpdateOpcode = {0b001, 3}; + +// Symbol code table from RFC 7541, "Appendix C. Huffman Code". +SPDY_EXPORT_PRIVATE const std::vector<HpackHuffmanSymbol>& +HpackHuffmanCodeVector(); + +// Static table from RFC 7541, "Appendix B. Static Table Definition". +SPDY_EXPORT_PRIVATE const std::vector<HpackStaticEntry>& +HpackStaticTableVector(); + +// Returns a HpackHuffmanTable instance initialized with |kHpackHuffmanCode|. +// The instance is read-only, has static lifetime, and is safe to share amoung +// threads. This function is thread-safe. +SPDY_EXPORT_PRIVATE const HpackHuffmanTable& ObtainHpackHuffmanTable(); + +// Returns a HpackStaticTable instance initialized with |kHpackStaticTable|. +// The instance is read-only, has static lifetime, and is safe to share amoung +// threads. This function is thread-safe. +SPDY_EXPORT_PRIVATE const HpackStaticTable& ObtainHpackStaticTable(); + +// Pseudo-headers start with a colon. (HTTP2 8.1.2.1., HPACK 3.1.) +const char kPseudoHeaderPrefix = ':'; + +} // namespace spdy + +#endif // QUICHE_SPDY_CORE_HPACK_HPACK_CONSTANTS_H_
diff --git a/spdy/core/hpack/hpack_decoder_adapter.cc b/spdy/core/hpack/hpack_decoder_adapter.cc new file mode 100644 index 0000000..309af39 --- /dev/null +++ b/spdy/core/hpack/hpack_decoder_adapter.cc
@@ -0,0 +1,201 @@ +// Copyright 2017 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_decoder_adapter.h" + +#include "base/logging.h" +#include "net/third_party/quiche/src/http2/decoder/decode_buffer.h" +#include "net/third_party/quiche/src/http2/decoder/decode_status.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_estimate_memory_usage.h" + +using ::http2::DecodeBuffer; +using ::http2::HpackEntryType; +using ::http2::HpackString; + +namespace spdy { +namespace { +const size_t kMaxDecodeBufferSizeBytes = 32 * 1024; // 32 KB +} // namespace + +HpackDecoderAdapter::HpackDecoderAdapter() + : hpack_decoder_(&listener_adapter_, kMaxDecodeBufferSizeBytes), + max_decode_buffer_size_bytes_(kMaxDecodeBufferSizeBytes), + header_block_started_(false) {} + +HpackDecoderAdapter::~HpackDecoderAdapter() = default; + +void HpackDecoderAdapter::ApplyHeaderTableSizeSetting(size_t size_setting) { + DVLOG(2) << "HpackDecoderAdapter::ApplyHeaderTableSizeSetting"; + hpack_decoder_.ApplyHeaderTableSizeSetting(size_setting); +} + +void HpackDecoderAdapter::HandleControlFrameHeadersStart( + SpdyHeadersHandlerInterface* handler) { + DVLOG(2) << "HpackDecoderAdapter::HandleControlFrameHeadersStart"; + DCHECK(!header_block_started_); + listener_adapter_.set_handler(handler); +} + +bool HpackDecoderAdapter::HandleControlFrameHeadersData( + const char* headers_data, + size_t headers_data_length) { + DVLOG(2) << "HpackDecoderAdapter::HandleControlFrameHeadersData: len=" + << headers_data_length; + if (!header_block_started_) { + // Initialize the decoding process here rather than in + // HandleControlFrameHeadersStart because that method is not always called. + header_block_started_ = true; + if (!hpack_decoder_.StartDecodingBlock()) { + header_block_started_ = false; + return false; + } + } + + // Sometimes we get a call with headers_data==nullptr and + // headers_data_length==0, in which case we need to avoid creating + // a DecodeBuffer, which would otherwise complain. + if (headers_data_length > 0) { + DCHECK_NE(headers_data, nullptr); + if (headers_data_length > max_decode_buffer_size_bytes_) { + DVLOG(1) << "max_decode_buffer_size_bytes_ < headers_data_length: " + << max_decode_buffer_size_bytes_ << " < " << headers_data_length; + return false; + } + listener_adapter_.AddToTotalHpackBytes(headers_data_length); + http2::DecodeBuffer db(headers_data, headers_data_length); + bool ok = hpack_decoder_.DecodeFragment(&db); + DCHECK(!ok || db.Empty()) << "Remaining=" << db.Remaining(); + return ok; + } + return true; +} + +bool HpackDecoderAdapter::HandleControlFrameHeadersComplete( + size_t* compressed_len) { + DVLOG(2) << "HpackDecoderAdapter::HandleControlFrameHeadersComplete"; + if (compressed_len != nullptr) { + *compressed_len = listener_adapter_.total_hpack_bytes(); + } + if (!hpack_decoder_.EndDecodingBlock()) { + DVLOG(3) << "EndDecodingBlock returned false"; + return false; + } + header_block_started_ = false; + return true; +} + +const SpdyHeaderBlock& HpackDecoderAdapter::decoded_block() const { + return listener_adapter_.decoded_block(); +} + +void HpackDecoderAdapter::SetHeaderTableDebugVisitor( + std::unique_ptr<HpackHeaderTable::DebugVisitorInterface> visitor) { + DVLOG(2) << "HpackDecoderAdapter::SetHeaderTableDebugVisitor"; + if (visitor != nullptr) { + listener_adapter_.SetHeaderTableDebugVisitor(std::move(visitor)); + hpack_decoder_.set_tables_debug_listener(&listener_adapter_); + } else { + hpack_decoder_.set_tables_debug_listener(nullptr); + listener_adapter_.SetHeaderTableDebugVisitor(nullptr); + } +} + +void HpackDecoderAdapter::set_max_decode_buffer_size_bytes( + size_t max_decode_buffer_size_bytes) { + DVLOG(2) << "HpackDecoderAdapter::set_max_decode_buffer_size_bytes"; + max_decode_buffer_size_bytes_ = max_decode_buffer_size_bytes; + hpack_decoder_.set_max_string_size_bytes(max_decode_buffer_size_bytes); +} + +size_t HpackDecoderAdapter::EstimateMemoryUsage() const { + return SpdyEstimateMemoryUsage(hpack_decoder_); +} + +HpackDecoderAdapter::ListenerAdapter::ListenerAdapter() : handler_(nullptr) {} +HpackDecoderAdapter::ListenerAdapter::~ListenerAdapter() = default; + +void HpackDecoderAdapter::ListenerAdapter::set_handler( + SpdyHeadersHandlerInterface* handler) { + handler_ = handler; +} + +void HpackDecoderAdapter::ListenerAdapter::SetHeaderTableDebugVisitor( + std::unique_ptr<HpackHeaderTable::DebugVisitorInterface> visitor) { + visitor_ = std::move(visitor); +} + +void HpackDecoderAdapter::ListenerAdapter::OnHeaderListStart() { + DVLOG(2) << "HpackDecoderAdapter::ListenerAdapter::OnHeaderListStart"; + total_hpack_bytes_ = 0; + total_uncompressed_bytes_ = 0; + decoded_block_.clear(); + if (handler_ != nullptr) { + handler_->OnHeaderBlockStart(); + } +} + +void HpackDecoderAdapter::ListenerAdapter::OnHeader(HpackEntryType entry_type, + const HpackString& name, + const HpackString& value) { + DVLOG(2) << "HpackDecoderAdapter::ListenerAdapter::OnHeader:\n name: " << name + << "\n value: " << value; + total_uncompressed_bytes_ += name.size() + value.size(); + if (handler_ == nullptr) { + DVLOG(3) << "Adding to decoded_block"; + decoded_block_.AppendValueOrAddHeader(name.ToStringPiece(), + value.ToStringPiece()); + } else { + DVLOG(3) << "Passing to handler"; + handler_->OnHeader(name.ToStringPiece(), value.ToStringPiece()); + } +} + +void HpackDecoderAdapter::ListenerAdapter::OnHeaderListEnd() { + DVLOG(2) << "HpackDecoderAdapter::ListenerAdapter::OnHeaderListEnd"; + // We don't clear the SpdyHeaderBlock here to allow access to it until the + // next HPACK block is decoded. + if (handler_ != nullptr) { + handler_->OnHeaderBlockEnd(total_uncompressed_bytes_, total_hpack_bytes_); + handler_ = nullptr; + } +} + +void HpackDecoderAdapter::ListenerAdapter::OnHeaderErrorDetected( + SpdyStringPiece error_message) { + VLOG(1) << error_message; +} + +int64_t HpackDecoderAdapter::ListenerAdapter::OnEntryInserted( + const http2::HpackStringPair& sp, + size_t insert_count) { + DVLOG(2) << "HpackDecoderAdapter::ListenerAdapter::OnEntryInserted: " << sp + << ", insert_count=" << insert_count; + if (visitor_ == nullptr) { + return 0; + } + HpackEntry entry(sp.name.ToStringPiece(), sp.value.ToStringPiece(), + /*is_static*/ false, insert_count); + int64_t time_added = visitor_->OnNewEntry(entry); + DVLOG(2) + << "HpackDecoderAdapter::ListenerAdapter::OnEntryInserted: time_added=" + << time_added; + return time_added; +} + +void HpackDecoderAdapter::ListenerAdapter::OnUseEntry( + const http2::HpackStringPair& sp, + size_t insert_count, + int64_t time_added) { + DVLOG(2) << "HpackDecoderAdapter::ListenerAdapter::OnUseEntry: " << sp + << ", insert_count=" << insert_count + << ", time_added=" << time_added; + if (visitor_ != nullptr) { + HpackEntry entry(sp.name.ToStringPiece(), sp.value.ToStringPiece(), + /*is_static*/ false, insert_count); + entry.set_time_added(time_added); + visitor_->OnUseEntry(entry); + } +} + +} // namespace spdy
diff --git a/spdy/core/hpack/hpack_decoder_adapter.h b/spdy/core/hpack/hpack_decoder_adapter.h new file mode 100644 index 0000000..b497fe7 --- /dev/null +++ b/spdy/core/hpack/hpack_decoder_adapter.h
@@ -0,0 +1,159 @@ +// Copyright 2017 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#ifndef QUICHE_SPDY_CORE_HPACK_HPACK_DECODER_ADAPTER_H_ +#define QUICHE_SPDY_CORE_HPACK_HPACK_DECODER_ADAPTER_H_ + +// HpackDecoderAdapter uses http2::HpackDecoder to decode HPACK blocks into +// HTTP/2 header lists as outlined in http://tools.ietf.org/html/rfc7541. + +#include <stddef.h> + +#include <cstdint> +#include <memory> + +#include "base/macros.h" +#include "net/third_party/quiche/src/http2/hpack/decoder/hpack_decoder.h" +#include "net/third_party/quiche/src/http2/hpack/decoder/hpack_decoder_listener.h" +#include "net/third_party/quiche/src/http2/hpack/decoder/hpack_decoder_tables.h" +#include "net/third_party/quiche/src/http2/hpack/hpack_string.h" +#include "net/third_party/quiche/src/http2/hpack/http2_hpack_constants.h" +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_header_table.h" +#include "net/third_party/quiche/src/spdy/core/spdy_header_block.h" +#include "net/third_party/quiche/src/spdy/core/spdy_headers_handler_interface.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_export.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_string_piece.h" + +namespace spdy { +namespace test { +class HpackDecoderAdapterPeer; +} // namespace test + +class SPDY_EXPORT_PRIVATE HpackDecoderAdapter { + public: + friend test::HpackDecoderAdapterPeer; + HpackDecoderAdapter(); + HpackDecoderAdapter(const HpackDecoderAdapter&) = delete; + HpackDecoderAdapter& operator=(const HpackDecoderAdapter&) = delete; + ~HpackDecoderAdapter(); + + // Called upon acknowledgement of SETTINGS_HEADER_TABLE_SIZE. + void ApplyHeaderTableSizeSetting(size_t size_setting); + + // If a SpdyHeadersHandlerInterface is provided, the decoder will emit + // headers to it rather than accumulating them in a SpdyHeaderBlock. + // Does not take ownership of the handler, but does use the pointer until + // the current HPACK block is completely decoded. + void HandleControlFrameHeadersStart(SpdyHeadersHandlerInterface* handler); + + // Called as HPACK block fragments arrive. Returns false if an error occurred + // while decoding the block. Does not take ownership of headers_data. + bool HandleControlFrameHeadersData(const char* headers_data, + size_t headers_data_length); + + // Called after a HPACK block has been completely delivered via + // HandleControlFrameHeadersData(). Returns false if an error occurred. + // |compressed_len| if non-null will be set to the size of the encoded + // buffered block that was accumulated in HandleControlFrameHeadersData(), + // to support subsequent calculation of compression percentage. + // Discards the handler supplied at the start of decoding the block. + // TODO(jamessynge): Determine if compressed_len is needed; it is used to + // produce UUMA stat Net.SpdyHpackDecompressionPercentage, but only for + // deprecated SPDY3. + bool HandleControlFrameHeadersComplete(size_t* compressed_len); + + // Accessor for the most recently decoded headers block. Valid until the next + // call to HandleControlFrameHeadersData(). + // TODO(birenroy): Remove this method when all users of HpackDecoder specify + // a SpdyHeadersHandlerInterface. + const SpdyHeaderBlock& decoded_block() const; + + void SetHeaderTableDebugVisitor( + std::unique_ptr<HpackHeaderTable::DebugVisitorInterface> visitor); + + // Set how much encoded data this decoder is willing to buffer. + // TODO(jamessynge): Resolve definition of this value, as it is currently + // too tied to a single implementation. We probably want to limit one or more + // of these: individual name or value strings, header entries, the entire + // header list, or the HPACK block; we probably shouldn't care about the size + // of individual transport buffers. + void set_max_decode_buffer_size_bytes(size_t max_decode_buffer_size_bytes); + + size_t EstimateMemoryUsage() const; + + private: + class SPDY_EXPORT_PRIVATE ListenerAdapter + : public http2::HpackDecoderListener, + public http2::HpackDecoderTablesDebugListener { + public: + ListenerAdapter(); + ~ListenerAdapter() override; + + // If a SpdyHeadersHandlerInterface is provided, the decoder will emit + // headers to it rather than accumulating them in a SpdyHeaderBlock. + // Does not take ownership of the handler, but does use the pointer until + // the current HPACK block is completely decoded. + void set_handler(SpdyHeadersHandlerInterface* handler); + const SpdyHeaderBlock& decoded_block() const { return decoded_block_; } + + void SetHeaderTableDebugVisitor( + std::unique_ptr<HpackHeaderTable::DebugVisitorInterface> visitor); + + // Override the HpackDecoderListener methods: + void OnHeaderListStart() override; + void OnHeader(http2::HpackEntryType entry_type, + const http2::HpackString& name, + const http2::HpackString& value) override; + void OnHeaderListEnd() override; + void OnHeaderErrorDetected(SpdyStringPiece error_message) override; + + // Override the HpackDecoderTablesDebugListener methods: + int64_t OnEntryInserted(const http2::HpackStringPair& entry, + size_t insert_count) override; + void OnUseEntry(const http2::HpackStringPair& entry, + size_t insert_count, + int64_t insert_time) override; + + void AddToTotalHpackBytes(size_t delta) { total_hpack_bytes_ += delta; } + size_t total_hpack_bytes() const { return total_hpack_bytes_; } + + private: + // If the caller doesn't provide a handler, the header list is stored in + // this SpdyHeaderBlock. + SpdyHeaderBlock decoded_block_; + + // If non-NULL, handles decoded headers. Not owned. + SpdyHeadersHandlerInterface* handler_; + + // Total bytes that have been received as input (i.e. HPACK encoded) + // in the current HPACK block. + size_t total_hpack_bytes_; + + // Total bytes of the name and value strings in the current HPACK block. + size_t total_uncompressed_bytes_; + + // visitor_ is used by a QUIC experiment regarding HPACK; remove + // when the experiment is done. + std::unique_ptr<HpackHeaderTable::DebugVisitorInterface> visitor_; + }; + + // Converts calls to HpackDecoderListener into calls to + // SpdyHeadersHandlerInterface. + ListenerAdapter listener_adapter_; + + // The actual decoder. + http2::HpackDecoder hpack_decoder_; + + // How much encoded data this decoder is willing to buffer. + size_t max_decode_buffer_size_bytes_; + + // Flag to keep track of having seen the header block start. Needed at the + // moment because HandleControlFrameHeadersStart won't be called if a handler + // is not being provided by the caller. + bool header_block_started_; +}; + +} // namespace spdy + +#endif // QUICHE_SPDY_CORE_HPACK_HPACK_DECODER_ADAPTER_H_
diff --git a/spdy/core/hpack/hpack_decoder_adapter_test.cc b/spdy/core/hpack/hpack_decoder_adapter_test.cc new file mode 100644 index 0000000..765c2ea --- /dev/null +++ b/spdy/core/hpack/hpack_decoder_adapter_test.cc
@@ -0,0 +1,1097 @@ +// Copyright 2017 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_decoder_adapter.h" + +// Tests of HpackDecoderAdapter. + +#include <stdint.h> + +#include <tuple> +#include <utility> +#include <vector> + +#include "base/logging.h" +#include "testing/gmock/include/gmock/gmock.h" +#include "testing/gtest/include/gtest/gtest.h" +#include "net/third_party/quiche/src/http2/hpack/decoder/hpack_decoder_state.h" +#include "net/third_party/quiche/src/http2/hpack/decoder/hpack_decoder_tables.h" +#include "net/third_party/quiche/src/http2/hpack/tools/hpack_block_builder.h" +#include "net/third_party/quiche/src/http2/test_tools/http2_random.h" +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_constants.h" +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_encoder.h" +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_output_stream.h" +#include "net/third_party/quiche/src/spdy/core/spdy_test_utils.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_arraysize.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_string.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_string_utils.h" + +using ::http2::HpackEntryType; +using ::http2::HpackString; +using ::http2::HpackStringPair; +using ::http2::test::HpackBlockBuilder; +using ::http2::test::HpackDecoderPeer; +using ::testing::ElementsAre; +using ::testing::Pair; + +namespace http2 { +namespace test { + +class HpackDecoderStatePeer { + public: + static HpackDecoderTables* GetDecoderTables(HpackDecoderState* state) { + return &state->decoder_tables_; + } +}; + +class HpackDecoderPeer { + public: + static HpackDecoderState* GetDecoderState(HpackDecoder* decoder) { + return &decoder->decoder_state_; + } + static HpackDecoderTables* GetDecoderTables(HpackDecoder* decoder) { + return HpackDecoderStatePeer::GetDecoderTables(GetDecoderState(decoder)); + } +}; + +} // namespace test +} // namespace http2 + +namespace spdy { +namespace test { + +class HpackDecoderAdapterPeer { + public: + explicit HpackDecoderAdapterPeer(HpackDecoderAdapter* decoder) + : decoder_(decoder) {} + + void HandleHeaderRepresentation(SpdyStringPiece name, SpdyStringPiece value) { + decoder_->listener_adapter_.OnHeader(HpackEntryType::kIndexedLiteralHeader, + HpackString(name), HpackString(value)); + } + + http2::HpackDecoderTables* GetDecoderTables() { + return HpackDecoderPeer::GetDecoderTables(&decoder_->hpack_decoder_); + } + + const HpackStringPair* GetTableEntry(uint32_t index) { + return GetDecoderTables()->Lookup(index); + } + + size_t current_header_table_size() { + return GetDecoderTables()->current_header_table_size(); + } + + size_t header_table_size_limit() { + return GetDecoderTables()->header_table_size_limit(); + } + + void set_header_table_size_limit(size_t size) { + return GetDecoderTables()->DynamicTableSizeUpdate(size); + } + + private: + HpackDecoderAdapter* decoder_; +}; + +class HpackEncoderPeer { + public: + static void CookieToCrumbs(const HpackEncoder::Representation& cookie, + HpackEncoder::Representations* crumbs_out) { + HpackEncoder::CookieToCrumbs(cookie, crumbs_out); + } +}; + +namespace { + +const bool kNoCheckDecodedSize = false; +const char* kCookieKey = "cookie"; + +// Is HandleControlFrameHeadersStart to be called, and with what value? +enum StartChoice { START_WITH_HANDLER, START_WITHOUT_HANDLER, NO_START }; + +class HpackDecoderAdapterTest + : public ::testing::TestWithParam<std::tuple<StartChoice, bool>> { + protected: + HpackDecoderAdapterTest() : decoder_(), decoder_peer_(&decoder_) {} + + void SetUp() override { + std::tie(start_choice_, randomly_split_input_buffer_) = GetParam(); + } + + void HandleControlFrameHeadersStart() { + bytes_passed_in_ = 0; + switch (start_choice_) { + case START_WITH_HANDLER: + decoder_.HandleControlFrameHeadersStart(&handler_); + break; + case START_WITHOUT_HANDLER: + decoder_.HandleControlFrameHeadersStart(nullptr); + break; + case NO_START: + break; + } + } + + bool HandleControlFrameHeadersData(SpdyStringPiece str) { + VLOG(3) << "HandleControlFrameHeadersData:\n" << SpdyHexDump(str); + bytes_passed_in_ += str.size(); + return decoder_.HandleControlFrameHeadersData(str.data(), str.size()); + } + + bool HandleControlFrameHeadersComplete(size_t* size) { + bool rc = decoder_.HandleControlFrameHeadersComplete(size); + if (size != nullptr) { + EXPECT_EQ(*size, bytes_passed_in_); + } + return rc; + } + + bool DecodeHeaderBlock(SpdyStringPiece str, bool check_decoded_size = true) { + // Don't call this again if HandleControlFrameHeadersData failed previously. + EXPECT_FALSE(decode_has_failed_); + HandleControlFrameHeadersStart(); + if (randomly_split_input_buffer_) { + do { + // Decode some fragment of the remaining bytes. + size_t bytes = str.size(); + if (!str.empty()) { + bytes = random_.Uniform(str.size()) + 1; + } + EXPECT_LE(bytes, str.size()); + if (!HandleControlFrameHeadersData(str.substr(0, bytes))) { + decode_has_failed_ = true; + return false; + } + str.remove_prefix(bytes); + } while (!str.empty()); + } else if (!HandleControlFrameHeadersData(str)) { + decode_has_failed_ = true; + return false; + } + // Want to get out the number of compressed bytes that were decoded, + // so pass in a pointer if no handler. + size_t total_hpack_bytes = 0; + if (start_choice_ == START_WITH_HANDLER) { + if (!HandleControlFrameHeadersComplete(nullptr)) { + decode_has_failed_ = true; + return false; + } + total_hpack_bytes = handler_.compressed_header_bytes_parsed(); + } else { + if (!HandleControlFrameHeadersComplete(&total_hpack_bytes)) { + decode_has_failed_ = true; + return false; + } + } + EXPECT_EQ(total_hpack_bytes, bytes_passed_in_); + if (check_decoded_size && start_choice_ == START_WITH_HANDLER) { + EXPECT_EQ(handler_.header_bytes_parsed(), SizeOfHeaders(decoded_block())); + } + return true; + } + + bool EncodeAndDecodeDynamicTableSizeUpdates(size_t first, size_t second) { + HpackBlockBuilder hbb; + hbb.AppendDynamicTableSizeUpdate(first); + if (second != first) { + hbb.AppendDynamicTableSizeUpdate(second); + } + return DecodeHeaderBlock(hbb.buffer()); + } + + const SpdyHeaderBlock& decoded_block() const { + if (start_choice_ == START_WITH_HANDLER) { + return handler_.decoded_block(); + } else { + return decoder_.decoded_block(); + } + } + + static size_t SizeOfHeaders(const SpdyHeaderBlock& headers) { + size_t size = 0; + for (const auto& kv : headers) { + if (kv.first == kCookieKey) { + HpackEncoder::Representations crumbs; + HpackEncoderPeer::CookieToCrumbs(kv, &crumbs); + for (const auto& crumb : crumbs) { + size += crumb.first.size() + crumb.second.size(); + } + } else { + size += kv.first.size() + kv.second.size(); + } + } + return size; + } + + const SpdyHeaderBlock& DecodeBlockExpectingSuccess(SpdyStringPiece str) { + EXPECT_TRUE(DecodeHeaderBlock(str)); + return decoded_block(); + } + + void expectEntry(size_t index, + size_t size, + const SpdyString& name, + const SpdyString& value) { + const HpackStringPair* entry = decoder_peer_.GetTableEntry(index); + EXPECT_EQ(name, entry->name) << "index " << index; + EXPECT_EQ(value, entry->value); + EXPECT_EQ(size, entry->size()); + } + + SpdyHeaderBlock MakeHeaderBlock( + const std::vector<std::pair<SpdyString, SpdyString>>& headers) { + SpdyHeaderBlock result; + for (const auto& kv : headers) { + result.AppendValueOrAddHeader(kv.first, kv.second); + } + return result; + } + + http2::test::Http2Random random_; + HpackDecoderAdapter decoder_; + test::HpackDecoderAdapterPeer decoder_peer_; + TestHeadersHandler handler_; + StartChoice start_choice_; + bool randomly_split_input_buffer_; + bool decode_has_failed_ = false; + size_t bytes_passed_in_; +}; + +INSTANTIATE_TEST_CASE_P( + NoHandler, + HpackDecoderAdapterTest, + ::testing::Combine(::testing::Values(START_WITHOUT_HANDLER, NO_START), + ::testing::Bool())); + +INSTANTIATE_TEST_CASE_P( + WithHandler, + HpackDecoderAdapterTest, + ::testing::Combine(::testing::Values(START_WITH_HANDLER), + ::testing::Bool())); + +TEST_P(HpackDecoderAdapterTest, + AddHeaderDataWithHandleControlFrameHeadersData) { + // The hpack decode buffer size is limited in size. This test verifies that + // adding encoded data under that limit is accepted, and data that exceeds the + // limit is rejected. + HandleControlFrameHeadersStart(); + const size_t kMaxBufferSizeBytes = 50; + const SpdyString a_value = SpdyString(49, 'x'); + decoder_.set_max_decode_buffer_size_bytes(kMaxBufferSizeBytes); + HpackBlockBuilder hbb; + hbb.AppendLiteralNameAndValue(HpackEntryType::kNeverIndexedLiteralHeader, + false, "a", false, a_value); + const SpdyString& s = hbb.buffer(); + EXPECT_GT(s.size(), kMaxBufferSizeBytes); + + // Any one in input buffer must not exceed kMaxBufferSizeBytes. + EXPECT_TRUE(HandleControlFrameHeadersData(s.substr(0, s.size() / 2))); + EXPECT_TRUE(HandleControlFrameHeadersData(s.substr(s.size() / 2))); + + EXPECT_FALSE(HandleControlFrameHeadersData(s)); + SpdyHeaderBlock expected_block = MakeHeaderBlock({{"a", a_value}}); + EXPECT_EQ(expected_block, decoded_block()); +} + +TEST_P(HpackDecoderAdapterTest, NameTooLong) { + // Verify that a name longer than the allowed size generates an error. + const size_t kMaxBufferSizeBytes = 50; + const SpdyString name = SpdyString(2 * kMaxBufferSizeBytes, 'x'); + const SpdyString value = "abc"; + + decoder_.set_max_decode_buffer_size_bytes(kMaxBufferSizeBytes); + + HpackBlockBuilder hbb; + hbb.AppendLiteralNameAndValue(HpackEntryType::kNeverIndexedLiteralHeader, + false, name, false, value); + + const size_t fragment_size = (3 * kMaxBufferSizeBytes) / 2; + const SpdyString fragment = hbb.buffer().substr(0, fragment_size); + + HandleControlFrameHeadersStart(); + EXPECT_FALSE(HandleControlFrameHeadersData(fragment)); +} + +TEST_P(HpackDecoderAdapterTest, HeaderTooLongToBuffer) { + // Verify that a header longer than the allowed size generates an error if + // it isn't all in one input buffer. + const SpdyString name = "some-key"; + const SpdyString value = "some-value"; + const size_t kMaxBufferSizeBytes = name.size() + value.size() - 2; + decoder_.set_max_decode_buffer_size_bytes(kMaxBufferSizeBytes); + + HpackBlockBuilder hbb; + hbb.AppendLiteralNameAndValue(HpackEntryType::kNeverIndexedLiteralHeader, + false, name, false, value); + const size_t fragment_size = hbb.size() - 1; + const SpdyString fragment = hbb.buffer().substr(0, fragment_size); + + HandleControlFrameHeadersStart(); + EXPECT_FALSE(HandleControlFrameHeadersData(fragment)); +} + +// Decode with incomplete data in buffer. +TEST_P(HpackDecoderAdapterTest, DecodeWithIncompleteData) { + HandleControlFrameHeadersStart(); + + // No need to wait for more data. + EXPECT_TRUE(HandleControlFrameHeadersData("\x82\x85\x82")); + std::vector<std::pair<SpdyString, SpdyString>> expected_headers = { + {":method", "GET"}, {":path", "/index.html"}, {":method", "GET"}}; + + SpdyHeaderBlock expected_block1 = MakeHeaderBlock(expected_headers); + EXPECT_EQ(expected_block1, decoded_block()); + + // Full and partial headers, won't add partial to the headers. + EXPECT_TRUE( + HandleControlFrameHeadersData("\x40\x03goo" + "\x03gar\xbe\x40\x04spam")); + expected_headers.push_back({"goo", "gar"}); + expected_headers.push_back({"goo", "gar"}); + + SpdyHeaderBlock expected_block2 = MakeHeaderBlock(expected_headers); + EXPECT_EQ(expected_block2, decoded_block()); + + // Add the needed data. + EXPECT_TRUE(HandleControlFrameHeadersData("\x04gggs")); + + size_t size = 0; + EXPECT_TRUE(HandleControlFrameHeadersComplete(&size)); + EXPECT_EQ(24u, size); + + expected_headers.push_back({"spam", "gggs"}); + + SpdyHeaderBlock expected_block3 = MakeHeaderBlock(expected_headers); + EXPECT_EQ(expected_block3, decoded_block()); +} + +TEST_P(HpackDecoderAdapterTest, HandleHeaderRepresentation) { + // Make sure the decoder is properly initialized. + HandleControlFrameHeadersStart(); + HandleControlFrameHeadersData(""); + + // All cookie crumbs are joined. + decoder_peer_.HandleHeaderRepresentation("cookie", " part 1"); + decoder_peer_.HandleHeaderRepresentation("cookie", "part 2 "); + decoder_peer_.HandleHeaderRepresentation("cookie", "part3"); + + // Already-delimited headers are passed through. + decoder_peer_.HandleHeaderRepresentation("passed-through", + SpdyString("foo\0baz", 7)); + + // Other headers are joined on \0. Case matters. + decoder_peer_.HandleHeaderRepresentation("joined", "not joined"); + decoder_peer_.HandleHeaderRepresentation("joineD", "value 1"); + decoder_peer_.HandleHeaderRepresentation("joineD", "value 2"); + + // Empty headers remain empty. + decoder_peer_.HandleHeaderRepresentation("empty", ""); + + // Joined empty headers work as expected. + decoder_peer_.HandleHeaderRepresentation("empty-joined", ""); + decoder_peer_.HandleHeaderRepresentation("empty-joined", "foo"); + decoder_peer_.HandleHeaderRepresentation("empty-joined", ""); + decoder_peer_.HandleHeaderRepresentation("empty-joined", ""); + + // Non-contiguous cookie crumb. + decoder_peer_.HandleHeaderRepresentation("cookie", " fin!"); + + // Finish and emit all headers. + decoder_.HandleControlFrameHeadersComplete(nullptr); + + // Resulting decoded headers are in the same order as the inputs. + EXPECT_THAT( + decoded_block(), + ElementsAre(Pair("cookie", " part 1; part 2 ; part3; fin!"), + Pair("passed-through", SpdyStringPiece("foo\0baz", 7)), + Pair("joined", "not joined"), + Pair("joineD", SpdyStringPiece("value 1\0value 2", 15)), + Pair("empty", ""), + Pair("empty-joined", SpdyStringPiece("\0foo\0\0", 6)))); +} + +// Decoding indexed static table field should work. +TEST_P(HpackDecoderAdapterTest, IndexedHeaderStatic) { + // Reference static table entries #2 and #5. + const SpdyHeaderBlock& header_set1 = DecodeBlockExpectingSuccess("\x82\x85"); + SpdyHeaderBlock expected_header_set1; + expected_header_set1[":method"] = "GET"; + expected_header_set1[":path"] = "/index.html"; + EXPECT_EQ(expected_header_set1, header_set1); + + // Reference static table entry #2. + const SpdyHeaderBlock& header_set2 = DecodeBlockExpectingSuccess("\x82"); + SpdyHeaderBlock expected_header_set2; + expected_header_set2[":method"] = "GET"; + EXPECT_EQ(expected_header_set2, header_set2); +} + +TEST_P(HpackDecoderAdapterTest, IndexedHeaderDynamic) { + // First header block: add an entry to header table. + const SpdyHeaderBlock& header_set1 = DecodeBlockExpectingSuccess( + "\x40\x03" + "foo" + "\x03" + "bar"); + SpdyHeaderBlock expected_header_set1; + expected_header_set1["foo"] = "bar"; + EXPECT_EQ(expected_header_set1, header_set1); + + // Second header block: add another entry to header table. + const SpdyHeaderBlock& header_set2 = DecodeBlockExpectingSuccess( + "\xbe\x40\x04" + "spam" + "\x04" + "eggs"); + SpdyHeaderBlock expected_header_set2; + expected_header_set2["foo"] = "bar"; + expected_header_set2["spam"] = "eggs"; + EXPECT_EQ(expected_header_set2, header_set2); + + // Third header block: refer to most recently added entry. + const SpdyHeaderBlock& header_set3 = DecodeBlockExpectingSuccess("\xbe"); + SpdyHeaderBlock expected_header_set3; + expected_header_set3["spam"] = "eggs"; + EXPECT_EQ(expected_header_set3, header_set3); +} + +// Test a too-large indexed header. +TEST_P(HpackDecoderAdapterTest, InvalidIndexedHeader) { + // High-bit set, and a prefix of one more than the number of static entries. + EXPECT_FALSE(DecodeHeaderBlock("\xbe")); +} + +TEST_P(HpackDecoderAdapterTest, ContextUpdateMaximumSize) { + EXPECT_EQ(kDefaultHeaderTableSizeSetting, + decoder_peer_.header_table_size_limit()); + SpdyString input; + { + // Maximum-size update with size 126. Succeeds. + HpackOutputStream output_stream; + output_stream.AppendPrefix(kHeaderTableSizeUpdateOpcode); + output_stream.AppendUint32(126); + + output_stream.TakeString(&input); + EXPECT_TRUE(DecodeHeaderBlock(SpdyStringPiece(input))); + EXPECT_EQ(126u, decoder_peer_.header_table_size_limit()); + } + { + // Maximum-size update with kDefaultHeaderTableSizeSetting. Succeeds. + HpackOutputStream output_stream; + output_stream.AppendPrefix(kHeaderTableSizeUpdateOpcode); + output_stream.AppendUint32(kDefaultHeaderTableSizeSetting); + + output_stream.TakeString(&input); + EXPECT_TRUE(DecodeHeaderBlock(SpdyStringPiece(input))); + EXPECT_EQ(kDefaultHeaderTableSizeSetting, + decoder_peer_.header_table_size_limit()); + } + { + // Maximum-size update with kDefaultHeaderTableSizeSetting + 1. Fails. + HpackOutputStream output_stream; + output_stream.AppendPrefix(kHeaderTableSizeUpdateOpcode); + output_stream.AppendUint32(kDefaultHeaderTableSizeSetting + 1); + + output_stream.TakeString(&input); + EXPECT_FALSE(DecodeHeaderBlock(SpdyStringPiece(input))); + EXPECT_EQ(kDefaultHeaderTableSizeSetting, + decoder_peer_.header_table_size_limit()); + } +} + +// Two HeaderTableSizeUpdates may appear at the beginning of the block +TEST_P(HpackDecoderAdapterTest, TwoTableSizeUpdates) { + SpdyString input; + { + // Should accept two table size updates, update to second one + HpackOutputStream output_stream; + output_stream.AppendPrefix(kHeaderTableSizeUpdateOpcode); + output_stream.AppendUint32(0); + output_stream.AppendPrefix(kHeaderTableSizeUpdateOpcode); + output_stream.AppendUint32(122); + + output_stream.TakeString(&input); + EXPECT_TRUE(DecodeHeaderBlock(SpdyStringPiece(input))); + EXPECT_EQ(122u, decoder_peer_.header_table_size_limit()); + } +} + +// Three HeaderTableSizeUpdates should result in an error +TEST_P(HpackDecoderAdapterTest, ThreeTableSizeUpdatesError) { + SpdyString input; + { + // Should reject three table size updates, update to second one + HpackOutputStream output_stream; + output_stream.AppendPrefix(kHeaderTableSizeUpdateOpcode); + output_stream.AppendUint32(5); + output_stream.AppendPrefix(kHeaderTableSizeUpdateOpcode); + output_stream.AppendUint32(10); + output_stream.AppendPrefix(kHeaderTableSizeUpdateOpcode); + output_stream.AppendUint32(15); + + output_stream.TakeString(&input); + + EXPECT_FALSE(DecodeHeaderBlock(SpdyStringPiece(input))); + EXPECT_EQ(10u, decoder_peer_.header_table_size_limit()); + } +} + +// HeaderTableSizeUpdates may only appear at the beginning of the block +// Any other updates should result in an error +TEST_P(HpackDecoderAdapterTest, TableSizeUpdateSecondError) { + SpdyString input; + { + // Should reject a table size update appearing after a different entry + // The table size should remain as the default + HpackOutputStream output_stream; + output_stream.AppendBytes("\x82\x85"); + output_stream.AppendPrefix(kHeaderTableSizeUpdateOpcode); + output_stream.AppendUint32(123); + + output_stream.TakeString(&input); + + EXPECT_FALSE(DecodeHeaderBlock(SpdyStringPiece(input))); + EXPECT_EQ(kDefaultHeaderTableSizeSetting, + decoder_peer_.header_table_size_limit()); + } +} + +// HeaderTableSizeUpdates may only appear at the beginning of the block +// Any other updates should result in an error +TEST_P(HpackDecoderAdapterTest, TableSizeUpdateFirstThirdError) { + SpdyString input; + { + // Should reject the second table size update + // if a different entry appears after the first update + // The table size should update to the first but not the second + HpackOutputStream output_stream; + output_stream.AppendPrefix(kHeaderTableSizeUpdateOpcode); + output_stream.AppendUint32(60); + output_stream.AppendBytes("\x82\x85"); + output_stream.AppendPrefix(kHeaderTableSizeUpdateOpcode); + output_stream.AppendUint32(125); + + output_stream.TakeString(&input); + + EXPECT_FALSE(DecodeHeaderBlock(SpdyStringPiece(input))); + EXPECT_EQ(60u, decoder_peer_.header_table_size_limit()); + } +} + +// Decoding two valid encoded literal headers with no indexing should +// work. +TEST_P(HpackDecoderAdapterTest, LiteralHeaderNoIndexing) { + // First header with indexed name, second header with string literal + // name. + const char input[] = "\x04\x0c/sample/path\x00\x06:path2\x0e/sample/path/2"; + const SpdyHeaderBlock& header_set = DecodeBlockExpectingSuccess( + SpdyStringPiece(input, SPDY_ARRAYSIZE(input) - 1)); + + SpdyHeaderBlock expected_header_set; + expected_header_set[":path"] = "/sample/path"; + expected_header_set[":path2"] = "/sample/path/2"; + EXPECT_EQ(expected_header_set, header_set); +} + +// Decoding two valid encoded literal headers with incremental +// indexing and string literal names should work. +TEST_P(HpackDecoderAdapterTest, LiteralHeaderIncrementalIndexing) { + const char input[] = "\x44\x0c/sample/path\x40\x06:path2\x0e/sample/path/2"; + const SpdyHeaderBlock& header_set = DecodeBlockExpectingSuccess( + SpdyStringPiece(input, SPDY_ARRAYSIZE(input) - 1)); + + SpdyHeaderBlock expected_header_set; + expected_header_set[":path"] = "/sample/path"; + expected_header_set[":path2"] = "/sample/path/2"; + EXPECT_EQ(expected_header_set, header_set); +} + +TEST_P(HpackDecoderAdapterTest, LiteralHeaderWithIndexingInvalidNameIndex) { + decoder_.ApplyHeaderTableSizeSetting(0); + EXPECT_TRUE(EncodeAndDecodeDynamicTableSizeUpdates(0, 0)); + + // Name is the last static index. Works. + EXPECT_TRUE(DecodeHeaderBlock(SpdyStringPiece("\x7d\x03ooo"))); + // Name is one beyond the last static index. Fails. + EXPECT_FALSE(DecodeHeaderBlock(SpdyStringPiece("\x7e\x03ooo"))); +} + +TEST_P(HpackDecoderAdapterTest, LiteralHeaderNoIndexingInvalidNameIndex) { + // Name is the last static index. Works. + EXPECT_TRUE(DecodeHeaderBlock(SpdyStringPiece("\x0f\x2e\x03ooo"))); + // Name is one beyond the last static index. Fails. + EXPECT_FALSE(DecodeHeaderBlock(SpdyStringPiece("\x0f\x2f\x03ooo"))); +} + +TEST_P(HpackDecoderAdapterTest, LiteralHeaderNeverIndexedInvalidNameIndex) { + // Name is the last static index. Works. + EXPECT_TRUE(DecodeHeaderBlock(SpdyStringPiece("\x1f\x2e\x03ooo"))); + // Name is one beyond the last static index. Fails. + EXPECT_FALSE(DecodeHeaderBlock(SpdyStringPiece("\x1f\x2f\x03ooo"))); +} + +TEST_P(HpackDecoderAdapterTest, TruncatedIndex) { + // Indexed Header, varint for index requires multiple bytes, + // but only one provided. + EXPECT_FALSE(DecodeHeaderBlock("\xff")); +} + +TEST_P(HpackDecoderAdapterTest, TruncatedHuffmanLiteral) { + // Literal value, Huffman encoded, but with the last byte missing (i.e. + // drop the final ff shown below). + // + // 41 | == Literal indexed == + // | Indexed name (idx = 1) + // | :authority + // 8c | Literal value (len = 12) + // | Huffman encoded: + // f1e3 c2e5 f23a 6ba0 ab90 f4ff | .....:k..... + // | Decoded: + // | www.example.com + // | -> :authority: www.example.com + + SpdyString first = SpdyHexDecode("418cf1e3c2e5f23a6ba0ab90f4ff"); + EXPECT_TRUE(DecodeHeaderBlock(first)); + first.pop_back(); + EXPECT_FALSE(DecodeHeaderBlock(first)); +} + +TEST_P(HpackDecoderAdapterTest, HuffmanEOSError) { + // Literal value, Huffman encoded, but with an additional ff byte at the end + // of the string, i.e. an EOS that is longer than permitted. + // + // 41 | == Literal indexed == + // | Indexed name (idx = 1) + // | :authority + // 8d | Literal value (len = 13) + // | Huffman encoded: + // f1e3 c2e5 f23a 6ba0 ab90 f4ff | .....:k..... + // | Decoded: + // | www.example.com + // | -> :authority: www.example.com + + SpdyString first = SpdyHexDecode("418cf1e3c2e5f23a6ba0ab90f4ff"); + EXPECT_TRUE(DecodeHeaderBlock(first)); + first = SpdyHexDecode("418df1e3c2e5f23a6ba0ab90f4ffff"); + EXPECT_FALSE(DecodeHeaderBlock(first)); +} + +// Round-tripping the header set from RFC 7541 C.3.1 should work. +// http://httpwg.org/specs/rfc7541.html#rfc.section.C.3.1 +TEST_P(HpackDecoderAdapterTest, BasicC31) { + HpackEncoder encoder(ObtainHpackHuffmanTable()); + + SpdyHeaderBlock expected_header_set; + expected_header_set[":method"] = "GET"; + expected_header_set[":scheme"] = "http"; + expected_header_set[":path"] = "/"; + expected_header_set[":authority"] = "www.example.com"; + + SpdyString encoded_header_set; + EXPECT_TRUE( + encoder.EncodeHeaderSet(expected_header_set, &encoded_header_set)); + + EXPECT_TRUE(DecodeHeaderBlock(encoded_header_set)); + EXPECT_EQ(expected_header_set, decoded_block()); +} + +// RFC 7541, Section C.4: Request Examples with Huffman Coding +// http://httpwg.org/specs/rfc7541.html#rfc.section.C.4 +TEST_P(HpackDecoderAdapterTest, SectionC4RequestHuffmanExamples) { + // TODO(jamessynge): Use http2/hpack/tools/hpack_example.h to parse the + // example directly, instead of having it as a comment. + // + // 82 | == Indexed - Add == + // | idx = 2 + // | -> :method: GET + // 86 | == Indexed - Add == + // | idx = 6 + // | -> :scheme: http + // 84 | == Indexed - Add == + // | idx = 4 + // | -> :path: / + // 41 | == Literal indexed == + // | Indexed name (idx = 1) + // | :authority + // 8c | Literal value (len = 12) + // | Huffman encoded: + // f1e3 c2e5 f23a 6ba0 ab90 f4ff | .....:k..... + // | Decoded: + // | www.example.com + // | -> :authority: www.example.com + SpdyString first = SpdyHexDecode("828684418cf1e3c2e5f23a6ba0ab90f4ff"); + const SpdyHeaderBlock& first_header_set = DecodeBlockExpectingSuccess(first); + + EXPECT_THAT(first_header_set, + ElementsAre( + // clang-format off + Pair(":method", "GET"), + Pair(":scheme", "http"), + Pair(":path", "/"), + Pair(":authority", "www.example.com"))); + // clang-format on + + expectEntry(62, 57, ":authority", "www.example.com"); + EXPECT_EQ(57u, decoder_peer_.current_header_table_size()); + + // 82 | == Indexed - Add == + // | idx = 2 + // | -> :method: GET + // 86 | == Indexed - Add == + // | idx = 6 + // | -> :scheme: http + // 84 | == Indexed - Add == + // | idx = 4 + // | -> :path: / + // be | == Indexed - Add == + // | idx = 62 + // | -> :authority: www.example.com + // 58 | == Literal indexed == + // | Indexed name (idx = 24) + // | cache-control + // 86 | Literal value (len = 8) + // | Huffman encoded: + // a8eb 1064 9cbf | ...d.. + // | Decoded: + // | no-cache + // | -> cache-control: no-cache + + SpdyString second = SpdyHexDecode("828684be5886a8eb10649cbf"); + const SpdyHeaderBlock& second_header_set = + DecodeBlockExpectingSuccess(second); + + EXPECT_THAT(second_header_set, + ElementsAre( + // clang-format off + Pair(":method", "GET"), + Pair(":scheme", "http"), + Pair(":path", "/"), + Pair(":authority", "www.example.com"), + Pair("cache-control", "no-cache"))); + // clang-format on + + expectEntry(62, 53, "cache-control", "no-cache"); + expectEntry(63, 57, ":authority", "www.example.com"); + EXPECT_EQ(110u, decoder_peer_.current_header_table_size()); + + // 82 | == Indexed - Add == + // | idx = 2 + // | -> :method: GET + // 87 | == Indexed - Add == + // | idx = 7 + // | -> :scheme: https + // 85 | == Indexed - Add == + // | idx = 5 + // | -> :path: /index.html + // bf | == Indexed - Add == + // | idx = 63 + // | -> :authority: www.example.com + // 40 | == Literal indexed == + // 88 | Literal name (len = 10) + // | Huffman encoded: + // 25a8 49e9 5ba9 7d7f | %.I.[.}. + // | Decoded: + // | custom-key + // 89 | Literal value (len = 12) + // | Huffman encoded: + // 25a8 49e9 5bb8 e8b4 bf | %.I.[.... + // | Decoded: + // | custom-value + // | -> custom-key: custom-value + SpdyString third = + SpdyHexDecode("828785bf408825a849e95ba97d7f8925a849e95bb8e8b4bf"); + const SpdyHeaderBlock& third_header_set = DecodeBlockExpectingSuccess(third); + + EXPECT_THAT( + third_header_set, + ElementsAre( + // clang-format off + Pair(":method", "GET"), + Pair(":scheme", "https"), + Pair(":path", "/index.html"), + Pair(":authority", "www.example.com"), + Pair("custom-key", "custom-value"))); + // clang-format on + + expectEntry(62, 54, "custom-key", "custom-value"); + expectEntry(63, 53, "cache-control", "no-cache"); + expectEntry(64, 57, ":authority", "www.example.com"); + EXPECT_EQ(164u, decoder_peer_.current_header_table_size()); +} + +// RFC 7541, Section C.6: Response Examples with Huffman Coding +// http://httpwg.org/specs/rfc7541.html#rfc.section.C.6 +TEST_P(HpackDecoderAdapterTest, SectionC6ResponseHuffmanExamples) { + // The example is based on a maximum dynamic table size of 256, + // which allows for testing dynamic table evictions. + decoder_peer_.set_header_table_size_limit(256); + + // 48 | == Literal indexed == + // | Indexed name (idx = 8) + // | :status + // 82 | Literal value (len = 3) + // | Huffman encoded: + // 6402 | d. + // | Decoded: + // | 302 + // | -> :status: 302 + // 58 | == Literal indexed == + // | Indexed name (idx = 24) + // | cache-control + // 85 | Literal value (len = 7) + // | Huffman encoded: + // aec3 771a 4b | ..w.K + // | Decoded: + // | private + // | -> cache-control: private + // 61 | == Literal indexed == + // | Indexed name (idx = 33) + // | date + // 96 | Literal value (len = 29) + // | Huffman encoded: + // d07a be94 1054 d444 a820 0595 040b 8166 | .z...T.D. .....f + // e082 a62d 1bff | ...-.. + // | Decoded: + // | Mon, 21 Oct 2013 20:13:21 + // | GMT + // | -> date: Mon, 21 Oct 2013 + // | 20:13:21 GMT + // 6e | == Literal indexed == + // | Indexed name (idx = 46) + // | location + // 91 | Literal value (len = 23) + // | Huffman encoded: + // 9d29 ad17 1863 c78f 0b97 c8e9 ae82 ae43 | .)...c.........C + // d3 | . + // | Decoded: + // | https://www.example.com + // | -> location: https://www.e + // | xample.com + + SpdyString first = SpdyHexDecode( + "488264025885aec3771a4b6196d07abe" + "941054d444a8200595040b8166e082a6" + "2d1bff6e919d29ad171863c78f0b97c8" + "e9ae82ae43d3"); + const SpdyHeaderBlock& first_header_set = DecodeBlockExpectingSuccess(first); + + EXPECT_THAT(first_header_set, + ElementsAre( + // clang-format off + Pair(":status", "302"), + Pair("cache-control", "private"), + Pair("date", "Mon, 21 Oct 2013 20:13:21 GMT"), + Pair("location", "https://www.example.com"))); + // clang-format on + + expectEntry(62, 63, "location", "https://www.example.com"); + expectEntry(63, 65, "date", "Mon, 21 Oct 2013 20:13:21 GMT"); + expectEntry(64, 52, "cache-control", "private"); + expectEntry(65, 42, ":status", "302"); + EXPECT_EQ(222u, decoder_peer_.current_header_table_size()); + + // 48 | == Literal indexed == + // | Indexed name (idx = 8) + // | :status + // 83 | Literal value (len = 3) + // | Huffman encoded: + // 640e ff | d.. + // | Decoded: + // | 307 + // | - evict: :status: 302 + // | -> :status: 307 + // c1 | == Indexed - Add == + // | idx = 65 + // | -> cache-control: private + // c0 | == Indexed - Add == + // | idx = 64 + // | -> date: Mon, 21 Oct 2013 + // | 20:13:21 GMT + // bf | == Indexed - Add == + // | idx = 63 + // | -> location: + // | https://www.example.com + SpdyString second = SpdyHexDecode("4883640effc1c0bf"); + const SpdyHeaderBlock& second_header_set = + DecodeBlockExpectingSuccess(second); + + EXPECT_THAT(second_header_set, + ElementsAre( + // clang-format off + Pair(":status", "307"), + Pair("cache-control", "private"), + Pair("date", "Mon, 21 Oct 2013 20:13:21 GMT"), + Pair("location", "https://www.example.com"))); + // clang-format on + + expectEntry(62, 42, ":status", "307"); + expectEntry(63, 63, "location", "https://www.example.com"); + expectEntry(64, 65, "date", "Mon, 21 Oct 2013 20:13:21 GMT"); + expectEntry(65, 52, "cache-control", "private"); + EXPECT_EQ(222u, decoder_peer_.current_header_table_size()); + + // 88 | == Indexed - Add == + // | idx = 8 + // | -> :status: 200 + // c1 | == Indexed - Add == + // | idx = 65 + // | -> cache-control: private + // 61 | == Literal indexed == + // | Indexed name (idx = 33) + // | date + // 96 | Literal value (len = 22) + // | Huffman encoded: + // d07a be94 1054 d444 a820 0595 040b 8166 | .z...T.D. .....f + // e084 a62d 1bff | ...-.. + // | Decoded: + // | Mon, 21 Oct 2013 20:13:22 + // | GMT + // | - evict: cache-control: + // | private + // | -> date: Mon, 21 Oct 2013 + // | 20:13:22 GMT + // c0 | == Indexed - Add == + // | idx = 64 + // | -> location: + // | https://www.example.com + // 5a | == Literal indexed == + // | Indexed name (idx = 26) + // | content-encoding + // 83 | Literal value (len = 3) + // | Huffman encoded: + // 9bd9 ab | ... + // | Decoded: + // | gzip + // | - evict: date: Mon, 21 Oct + // | 2013 20:13:21 GMT + // | -> content-encoding: gzip + // 77 | == Literal indexed == + // | Indexed name (idx = 55) + // | set-cookie + // ad | Literal value (len = 45) + // | Huffman encoded: + // 94e7 821d d7f2 e6c7 b335 dfdf cd5b 3960 | .........5...[9` + // d5af 2708 7f36 72c1 ab27 0fb5 291f 9587 | ..'..6r..'..)... + // 3160 65c0 03ed 4ee5 b106 3d50 07 | 1`e...N...=P. + // | Decoded: + // | foo=ASDJKHQKBZXOQWEOPIUAXQ + // | WEOIU; max-age=3600; versi + // | on=1 + // | - evict: location: + // | https://www.example.com + // | - evict: :status: 307 + // | -> set-cookie: foo=ASDJKHQ + // | KBZXOQWEOPIUAXQWEOIU; + // | max-age=3600; version=1 + SpdyString third = SpdyHexDecode( + "88c16196d07abe941054d444a8200595" + "040b8166e084a62d1bffc05a839bd9ab" + "77ad94e7821dd7f2e6c7b335dfdfcd5b" + "3960d5af27087f3672c1ab270fb5291f" + "9587316065c003ed4ee5b1063d5007"); + const SpdyHeaderBlock& third_header_set = DecodeBlockExpectingSuccess(third); + + EXPECT_THAT(third_header_set, + ElementsAre( + // clang-format off + Pair(":status", "200"), + Pair("cache-control", "private"), + Pair("date", "Mon, 21 Oct 2013 20:13:22 GMT"), + Pair("location", "https://www.example.com"), + Pair("content-encoding", "gzip"), + Pair("set-cookie", "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU;" + " max-age=3600; version=1"))); + // clang-format on + + expectEntry(62, 98, "set-cookie", + "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU;" + " max-age=3600; version=1"); + expectEntry(63, 52, "content-encoding", "gzip"); + expectEntry(64, 65, "date", "Mon, 21 Oct 2013 20:13:22 GMT"); + EXPECT_EQ(215u, decoder_peer_.current_header_table_size()); +} + +// Regression test: Found that entries with dynamic indexed names and literal +// values caused "use after free" MSAN failures if the name was evicted as it +// was being re-used. +TEST_P(HpackDecoderAdapterTest, ReuseNameOfEvictedEntry) { + // Each entry is measured as 32 bytes plus the sum of the lengths of the name + // and the value. Set the size big enough for at most one entry, and a fairly + // small one at that (31 ASCII characters). + decoder_.ApplyHeaderTableSizeSetting(63); + + HpackBlockBuilder hbb; + hbb.AppendDynamicTableSizeUpdate(0); + hbb.AppendDynamicTableSizeUpdate(63); + + const SpdyStringPiece name("some-name"); + const SpdyStringPiece value1("some-value"); + const SpdyStringPiece value2("another-value"); + const SpdyStringPiece value3("yet-another-value"); + + // Add an entry that will become the first in the dynamic table, entry 62. + hbb.AppendLiteralNameAndValue(HpackEntryType::kIndexedLiteralHeader, false, + name, false, value1); + + // Confirm that entry has been added by re-using it. + hbb.AppendIndexedHeader(62); + + // Add another entry referring to the name of the first. This will evict the + // first. + hbb.AppendNameIndexAndLiteralValue(HpackEntryType::kIndexedLiteralHeader, 62, + false, value2); + + // Confirm that entry has been added by re-using it. + hbb.AppendIndexedHeader(62); + + // Add another entry referring to the name of the second. This will evict the + // second. + hbb.AppendNameIndexAndLiteralValue(HpackEntryType::kIndexedLiteralHeader, 62, + false, value3); + + // Confirm that entry has been added by re-using it. + hbb.AppendIndexedHeader(62); + + // Can't have DecodeHeaderBlock do the default check for size of the decoded + // data because SpdyHeaderBlock will join multiple headers with the same + // name into a single entry, thus we won't see repeated occurrences of the + // name, instead seeing separators between values. + EXPECT_TRUE(DecodeHeaderBlock(hbb.buffer(), kNoCheckDecodedSize)); + + SpdyHeaderBlock expected_header_set; + expected_header_set.AppendValueOrAddHeader(name, value1); + expected_header_set.AppendValueOrAddHeader(name, value1); + expected_header_set.AppendValueOrAddHeader(name, value2); + expected_header_set.AppendValueOrAddHeader(name, value2); + expected_header_set.AppendValueOrAddHeader(name, value3); + expected_header_set.AppendValueOrAddHeader(name, value3); + + // SpdyHeaderBlock stores these 6 strings as '\0' separated values. + // Make sure that is what happened. + SpdyString joined_values = expected_header_set[name].as_string(); + EXPECT_EQ(joined_values.size(), + 2 * value1.size() + 2 * value2.size() + 2 * value3.size() + 5); + + EXPECT_EQ(expected_header_set, decoded_block()); + + if (start_choice_ == START_WITH_HANDLER) { + EXPECT_EQ(handler_.header_bytes_parsed(), + 6 * name.size() + 2 * value1.size() + 2 * value2.size() + + 2 * value3.size()); + } +} + +// Regression test for https://crbug.com/747395. +TEST_P(HpackDecoderAdapterTest, Cookies) { + SpdyHeaderBlock expected_header_set; + expected_header_set["cookie"] = "foo; bar"; + + EXPECT_TRUE(DecodeHeaderBlock(SpdyHexDecode("608294e76003626172"))); + EXPECT_EQ(expected_header_set, decoded_block()); +} + +} // namespace +} // namespace test +} // namespace spdy
diff --git a/spdy/core/hpack/hpack_encoder.cc b/spdy/core/hpack/hpack_encoder.cc new file mode 100644 index 0000000..a9981b9 --- /dev/null +++ b/spdy/core/hpack/hpack_encoder.cc
@@ -0,0 +1,365 @@ +// Copyright 2014 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_encoder.h" + +#include <algorithm> +#include <limits> + +#include "base/logging.h" +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_constants.h" +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_header_table.h" +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_huffman_table.h" +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_output_stream.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_estimate_memory_usage.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_ptr_util.h" + +namespace spdy { + +class HpackEncoder::RepresentationIterator { + public: + // |pseudo_headers| and |regular_headers| must outlive the iterator. + RepresentationIterator(const Representations& pseudo_headers, + const Representations& regular_headers) + : pseudo_begin_(pseudo_headers.begin()), + pseudo_end_(pseudo_headers.end()), + regular_begin_(regular_headers.begin()), + regular_end_(regular_headers.end()) {} + + // |headers| must outlive the iterator. + explicit RepresentationIterator(const Representations& headers) + : pseudo_begin_(headers.begin()), + pseudo_end_(headers.end()), + regular_begin_(headers.end()), + regular_end_(headers.end()) {} + + bool HasNext() { + return pseudo_begin_ != pseudo_end_ || regular_begin_ != regular_end_; + } + + const Representation Next() { + if (pseudo_begin_ != pseudo_end_) { + return *pseudo_begin_++; + } else { + return *regular_begin_++; + } + } + + private: + Representations::const_iterator pseudo_begin_; + Representations::const_iterator pseudo_end_; + Representations::const_iterator regular_begin_; + Representations::const_iterator regular_end_; +}; + +namespace { + +// The default header listener. +void NoOpListener(SpdyStringPiece /*name*/, SpdyStringPiece /*value*/) {} + +// The default HPACK indexing policy. +bool DefaultPolicy(SpdyStringPiece name, SpdyStringPiece /* value */) { + if (name.empty()) { + return false; + } + // :authority is always present and rarely changes, and has moderate + // length, therefore it makes a lot of sense to index (insert in the + // dynamic table). + if (name[0] == kPseudoHeaderPrefix) { + return name == ":authority"; + } + return true; +} + +} // namespace + +HpackEncoder::HpackEncoder(const HpackHuffmanTable& table) + : output_stream_(), + huffman_table_(table), + min_table_size_setting_received_(std::numeric_limits<size_t>::max()), + listener_(NoOpListener), + should_index_(DefaultPolicy), + enable_compression_(true), + should_emit_table_size_(false) {} + +HpackEncoder::~HpackEncoder() = default; + +bool HpackEncoder::EncodeHeaderSet(const SpdyHeaderBlock& header_set, + SpdyString* output) { + // Separate header set into pseudo-headers and regular headers. + Representations pseudo_headers; + Representations regular_headers; + bool found_cookie = false; + for (const auto& header : header_set) { + if (!found_cookie && header.first == "cookie") { + // Note that there can only be one "cookie" header, because header_set is + // a map. + found_cookie = true; + CookieToCrumbs(header, ®ular_headers); + } else if (!header.first.empty() && + header.first[0] == kPseudoHeaderPrefix) { + DecomposeRepresentation(header, &pseudo_headers); + } else { + DecomposeRepresentation(header, ®ular_headers); + } + } + + { + RepresentationIterator iter(pseudo_headers, regular_headers); + EncodeRepresentations(&iter, output); + } + return true; +} + +void HpackEncoder::ApplyHeaderTableSizeSetting(size_t size_setting) { + if (size_setting == header_table_.settings_size_bound()) { + return; + } + if (size_setting < header_table_.settings_size_bound()) { + min_table_size_setting_received_ = + std::min(size_setting, min_table_size_setting_received_); + } + header_table_.SetSettingsHeaderTableSize(size_setting); + should_emit_table_size_ = true; +} + +size_t HpackEncoder::EstimateMemoryUsage() const { + // |huffman_table_| is a singleton. It's accounted for in spdy_session_pool.cc + return SpdyEstimateMemoryUsage(header_table_) + + SpdyEstimateMemoryUsage(output_stream_); +} + +void HpackEncoder::EncodeRepresentations(RepresentationIterator* iter, + SpdyString* output) { + MaybeEmitTableSize(); + while (iter->HasNext()) { + const auto header = iter->Next(); + listener_(header.first, header.second); + if (enable_compression_) { + const HpackEntry* entry = + header_table_.GetByNameAndValue(header.first, header.second); + if (entry != nullptr) { + EmitIndex(entry); + } else if (should_index_(header.first, header.second)) { + EmitIndexedLiteral(header); + } else { + EmitNonIndexedLiteral(header); + } + } else { + EmitNonIndexedLiteral(header); + } + } + + output_stream_.TakeString(output); +} + +void HpackEncoder::EmitIndex(const HpackEntry* entry) { + DVLOG(2) << "Emitting index " << header_table_.IndexOf(entry); + output_stream_.AppendPrefix(kIndexedOpcode); + output_stream_.AppendUint32(header_table_.IndexOf(entry)); +} + +void HpackEncoder::EmitIndexedLiteral(const Representation& representation) { + DVLOG(2) << "Emitting indexed literal: (" << representation.first << ", " + << representation.second << ")"; + output_stream_.AppendPrefix(kLiteralIncrementalIndexOpcode); + EmitLiteral(representation); + header_table_.TryAddEntry(representation.first, representation.second); +} + +void HpackEncoder::EmitNonIndexedLiteral(const Representation& representation) { + DVLOG(2) << "Emitting nonindexed literal: (" << representation.first << ", " + << representation.second << ")"; + output_stream_.AppendPrefix(kLiteralNoIndexOpcode); + output_stream_.AppendUint32(0); + EmitString(representation.first); + EmitString(representation.second); +} + +void HpackEncoder::EmitLiteral(const Representation& representation) { + const HpackEntry* name_entry = header_table_.GetByName(representation.first); + if (name_entry != nullptr) { + output_stream_.AppendUint32(header_table_.IndexOf(name_entry)); + } else { + output_stream_.AppendUint32(0); + EmitString(representation.first); + } + EmitString(representation.second); +} + +void HpackEncoder::EmitString(SpdyStringPiece str) { + size_t encoded_size = + enable_compression_ ? huffman_table_.EncodedSize(str) : str.size(); + if (encoded_size < str.size()) { + DVLOG(2) << "Emitted Huffman-encoded string of length " << encoded_size; + output_stream_.AppendPrefix(kStringLiteralHuffmanEncoded); + output_stream_.AppendUint32(encoded_size); + huffman_table_.EncodeString(str, &output_stream_); + } else { + DVLOG(2) << "Emitted literal string of length " << str.size(); + output_stream_.AppendPrefix(kStringLiteralIdentityEncoded); + output_stream_.AppendUint32(str.size()); + output_stream_.AppendBytes(str); + } +} + +void HpackEncoder::MaybeEmitTableSize() { + if (!should_emit_table_size_) { + return; + } + const size_t current_size = CurrentHeaderTableSizeSetting(); + DVLOG(1) << "MaybeEmitTableSize current_size=" << current_size; + DVLOG(1) << "MaybeEmitTableSize min_table_size_setting_received_=" + << min_table_size_setting_received_; + if (min_table_size_setting_received_ < current_size) { + output_stream_.AppendPrefix(kHeaderTableSizeUpdateOpcode); + output_stream_.AppendUint32(min_table_size_setting_received_); + } + output_stream_.AppendPrefix(kHeaderTableSizeUpdateOpcode); + output_stream_.AppendUint32(current_size); + min_table_size_setting_received_ = std::numeric_limits<size_t>::max(); + should_emit_table_size_ = false; +} + +// static +void HpackEncoder::CookieToCrumbs(const Representation& cookie, + Representations* out) { + // See Section 8.1.2.5. "Compressing the Cookie Header Field" in the HTTP/2 + // specification at https://tools.ietf.org/html/draft-ietf-httpbis-http2-14. + // Cookie values are split into individually-encoded HPACK representations. + SpdyStringPiece cookie_value = cookie.second; + // Consume leading and trailing whitespace if present. + SpdyStringPiece::size_type first = cookie_value.find_first_not_of(" \t"); + SpdyStringPiece::size_type last = cookie_value.find_last_not_of(" \t"); + if (first == SpdyStringPiece::npos) { + cookie_value = SpdyStringPiece(); + } else { + cookie_value = cookie_value.substr(first, (last - first) + 1); + } + for (size_t pos = 0;;) { + size_t end = cookie_value.find(";", pos); + + if (end == SpdyStringPiece::npos) { + out->push_back(std::make_pair(cookie.first, cookie_value.substr(pos))); + break; + } + out->push_back( + std::make_pair(cookie.first, cookie_value.substr(pos, end - pos))); + + // Consume next space if present. + pos = end + 1; + if (pos != cookie_value.size() && cookie_value[pos] == ' ') { + pos++; + } + } +} + +// static +void HpackEncoder::DecomposeRepresentation(const Representation& header_field, + Representations* out) { + size_t pos = 0; + size_t end = 0; + while (end != SpdyStringPiece::npos) { + end = header_field.second.find('\0', pos); + out->push_back(std::make_pair( + header_field.first, + header_field.second.substr( + pos, end == SpdyStringPiece::npos ? end : end - pos))); + pos = end + 1; + } +} + +// static +void HpackEncoder::GatherRepresentation(const Representation& header_field, + Representations* out) { + out->push_back(std::make_pair(header_field.first, header_field.second)); +} + +// Iteratively encodes a SpdyHeaderBlock. +class HpackEncoder::Encoderator : public ProgressiveEncoder { + public: + Encoderator(const SpdyHeaderBlock& header_set, HpackEncoder* encoder); + + // Encoderator is neither copyable nor movable. + Encoderator(const Encoderator&) = delete; + Encoderator& operator=(const Encoderator&) = delete; + + // Returns true iff more remains to encode. + bool HasNext() const override { return has_next_; } + + // Encodes up to max_encoded_bytes of the current header block into the + // given output string. + void Next(size_t max_encoded_bytes, SpdyString* output) override; + + private: + HpackEncoder* encoder_; + std::unique_ptr<RepresentationIterator> header_it_; + Representations pseudo_headers_; + Representations regular_headers_; + bool has_next_; +}; + +HpackEncoder::Encoderator::Encoderator(const SpdyHeaderBlock& header_set, + HpackEncoder* encoder) + : encoder_(encoder), has_next_(true) { + // Separate header set into pseudo-headers and regular headers. + const bool use_compression = encoder_->enable_compression_; + bool found_cookie = false; + for (const auto& header : header_set) { + if (!found_cookie && header.first == "cookie") { + // Note that there can only be one "cookie" header, because header_set + // is a map. + found_cookie = true; + CookieToCrumbs(header, ®ular_headers_); + } else if (!header.first.empty() && + header.first[0] == kPseudoHeaderPrefix) { + use_compression ? DecomposeRepresentation(header, &pseudo_headers_) + : GatherRepresentation(header, &pseudo_headers_); + } else { + use_compression ? DecomposeRepresentation(header, ®ular_headers_) + : GatherRepresentation(header, ®ular_headers_); + } + } + header_it_ = + SpdyMakeUnique<RepresentationIterator>(pseudo_headers_, regular_headers_); + + encoder_->MaybeEmitTableSize(); +} + +void HpackEncoder::Encoderator::Next(size_t max_encoded_bytes, + SpdyString* output) { + SPDY_BUG_IF(!has_next_) + << "Encoderator::Next called with nothing left to encode."; + const bool use_compression = encoder_->enable_compression_; + + // Encode up to max_encoded_bytes of headers. + while (header_it_->HasNext() && + encoder_->output_stream_.size() <= max_encoded_bytes) { + const Representation header = header_it_->Next(); + encoder_->listener_(header.first, header.second); + if (use_compression) { + const HpackEntry* entry = encoder_->header_table_.GetByNameAndValue( + header.first, header.second); + if (entry != nullptr) { + encoder_->EmitIndex(entry); + } else if (encoder_->should_index_(header.first, header.second)) { + encoder_->EmitIndexedLiteral(header); + } else { + encoder_->EmitNonIndexedLiteral(header); + } + } else { + encoder_->EmitNonIndexedLiteral(header); + } + } + + has_next_ = encoder_->output_stream_.size() > max_encoded_bytes; + encoder_->output_stream_.BoundedTakeString(max_encoded_bytes, output); +} + +std::unique_ptr<HpackEncoder::ProgressiveEncoder> HpackEncoder::EncodeHeaderSet( + const SpdyHeaderBlock& header_set) { + return SpdyMakeUnique<Encoderator>(header_set, this); +} + +} // namespace spdy
diff --git a/spdy/core/hpack/hpack_encoder.h b/spdy/core/hpack/hpack_encoder.h new file mode 100644 index 0000000..486d536 --- /dev/null +++ b/spdy/core/hpack/hpack_encoder.h
@@ -0,0 +1,152 @@ +// Copyright 2014 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#ifndef QUICHE_SPDY_CORE_HPACK_HPACK_ENCODER_H_ +#define QUICHE_SPDY_CORE_HPACK_HPACK_ENCODER_H_ + +#include <stddef.h> + +#include <functional> +#include <map> +#include <memory> +#include <utility> +#include <vector> + +#include "base/macros.h" +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_header_table.h" +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_output_stream.h" +#include "net/third_party/quiche/src/spdy/core/spdy_protocol.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_export.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_string.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_string_piece.h" + +// An HpackEncoder encodes header sets as outlined in +// http://tools.ietf.org/html/rfc7541. + +namespace spdy { + +class HpackHuffmanTable; + +namespace test { +class HpackEncoderPeer; +} // namespace test + +class SPDY_EXPORT_PRIVATE HpackEncoder { + public: + using Representation = std::pair<SpdyStringPiece, SpdyStringPiece>; + using Representations = std::vector<Representation>; + + // Callers may provide a HeaderListener to be informed of header name-value + // pairs processed by this encoder. + using HeaderListener = std::function<void(SpdyStringPiece, SpdyStringPiece)>; + + // An indexing policy should return true if the provided header name-value + // pair should be inserted into the HPACK dynamic table. + using IndexingPolicy = std::function<bool(SpdyStringPiece, SpdyStringPiece)>; + + // |table| is an initialized HPACK Huffman table, having an + // externally-managed lifetime which spans beyond HpackEncoder. + explicit HpackEncoder(const HpackHuffmanTable& table); + HpackEncoder(const HpackEncoder&) = delete; + HpackEncoder& operator=(const HpackEncoder&) = delete; + ~HpackEncoder(); + + // Encodes the given header set into the given string. Returns + // whether or not the encoding was successful. + bool EncodeHeaderSet(const SpdyHeaderBlock& header_set, SpdyString* output); + + class SPDY_EXPORT_PRIVATE ProgressiveEncoder { + public: + virtual ~ProgressiveEncoder() {} + + // Returns true iff more remains to encode. + virtual bool HasNext() const = 0; + + // Encodes up to max_encoded_bytes of the current header block into the + // given output string. + virtual void Next(size_t max_encoded_bytes, SpdyString* output) = 0; + }; + + // Returns a ProgressiveEncoder which must be outlived by both the given + // SpdyHeaderBlock and this object. + std::unique_ptr<ProgressiveEncoder> EncodeHeaderSet( + const SpdyHeaderBlock& header_set); + + // Called upon a change to SETTINGS_HEADER_TABLE_SIZE. Specifically, this + // is to be called after receiving (and sending an acknowledgement for) a + // SETTINGS_HEADER_TABLE_SIZE update from the remote decoding endpoint. + void ApplyHeaderTableSizeSetting(size_t size_setting); + + size_t CurrentHeaderTableSizeSetting() const { + return header_table_.settings_size_bound(); + } + + // This HpackEncoder will use |policy| to determine whether to insert header + // name-value pairs into the dynamic table. + void SetIndexingPolicy(IndexingPolicy policy) { should_index_ = policy; } + + // |listener| will be invoked for each header name-value pair processed by + // this encoder. + void SetHeaderListener(HeaderListener listener) { listener_ = listener; } + + void SetHeaderTableDebugVisitor( + std::unique_ptr<HpackHeaderTable::DebugVisitorInterface> visitor) { + header_table_.set_debug_visitor(std::move(visitor)); + } + + void DisableCompression() { enable_compression_ = false; } + + // Returns the estimate of dynamically allocated memory in bytes. + size_t EstimateMemoryUsage() const; + + private: + friend class test::HpackEncoderPeer; + + class RepresentationIterator; + class Encoderator; + + // Encodes a sequence of header name-value pairs as a single header block. + void EncodeRepresentations(RepresentationIterator* iter, SpdyString* output); + + // Emits a static/dynamic indexed representation (Section 7.1). + void EmitIndex(const HpackEntry* entry); + + // Emits a literal representation (Section 7.2). + void EmitIndexedLiteral(const Representation& representation); + void EmitNonIndexedLiteral(const Representation& representation); + void EmitLiteral(const Representation& representation); + + // Emits a Huffman or identity string (whichever is smaller). + void EmitString(SpdyStringPiece str); + + // Emits the current dynamic table size if the table size was recently + // updated and we have not yet emitted it (Section 6.3). + void MaybeEmitTableSize(); + + // Crumbles a cookie header into ";" delimited crumbs. + static void CookieToCrumbs(const Representation& cookie, + Representations* crumbs_out); + + // Crumbles other header field values at \0 delimiters. + static void DecomposeRepresentation(const Representation& header_field, + Representations* out); + + // Gathers headers without crumbling. Used when compression is not enabled. + static void GatherRepresentation(const Representation& header_field, + Representations* out); + + HpackHeaderTable header_table_; + HpackOutputStream output_stream_; + + const HpackHuffmanTable& huffman_table_; + size_t min_table_size_setting_received_; + HeaderListener listener_; + IndexingPolicy should_index_; + bool enable_compression_; + bool should_emit_table_size_; +}; + +} // namespace spdy + +#endif // QUICHE_SPDY_CORE_HPACK_HPACK_ENCODER_H_
diff --git a/spdy/core/hpack/hpack_encoder_test.cc b/spdy/core/hpack/hpack_encoder_test.cc new file mode 100644 index 0000000..8ead1c2 --- /dev/null +++ b/spdy/core/hpack/hpack_encoder_test.cc
@@ -0,0 +1,586 @@ +// Copyright 2014 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_encoder.h" + +#include <cstdint> +#include <map> + +#include "testing/gmock/include/gmock/gmock.h" +#include "testing/gtest/include/gtest/gtest.h" +#include "net/third_party/quiche/src/http2/test_tools/http2_random.h" +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_huffman_table.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_unsafe_arena.h" + +namespace spdy { + +namespace test { + +class HpackHeaderTablePeer { + public: + explicit HpackHeaderTablePeer(HpackHeaderTable* table) : table_(table) {} + + HpackHeaderTable::EntryTable* dynamic_entries() { + return &table_->dynamic_entries_; + } + + private: + HpackHeaderTable* table_; +}; + +class HpackEncoderPeer { + public: + typedef HpackEncoder::Representation Representation; + typedef HpackEncoder::Representations Representations; + + explicit HpackEncoderPeer(HpackEncoder* encoder) : encoder_(encoder) {} + + bool compression_enabled() const { return encoder_->enable_compression_; } + HpackHeaderTable* table() { return &encoder_->header_table_; } + HpackHeaderTablePeer table_peer() { return HpackHeaderTablePeer(table()); } + const HpackHuffmanTable& huffman_table() const { + return encoder_->huffman_table_; + } + void EmitString(SpdyStringPiece str) { encoder_->EmitString(str); } + void TakeString(SpdyString* out) { encoder_->output_stream_.TakeString(out); } + static void CookieToCrumbs(SpdyStringPiece cookie, + std::vector<SpdyStringPiece>* out) { + Representations tmp; + HpackEncoder::CookieToCrumbs(std::make_pair("", cookie), &tmp); + + out->clear(); + for (size_t i = 0; i != tmp.size(); ++i) { + out->push_back(tmp[i].second); + } + } + static void DecomposeRepresentation(SpdyStringPiece value, + std::vector<SpdyStringPiece>* out) { + Representations tmp; + HpackEncoder::DecomposeRepresentation(std::make_pair("foobar", value), + &tmp); + + out->clear(); + for (size_t i = 0; i != tmp.size(); ++i) { + out->push_back(tmp[i].second); + } + } + + // TODO(dahollings): Remove or clean up these methods when deprecating + // non-incremental encoding path. + static bool EncodeHeaderSet(HpackEncoder* encoder, + const SpdyHeaderBlock& header_set, + SpdyString* output, + bool use_incremental) { + if (use_incremental) { + return EncodeIncremental(encoder, header_set, output); + } else { + return encoder->EncodeHeaderSet(header_set, output); + } + } + + static bool EncodeIncremental(HpackEncoder* encoder, + const SpdyHeaderBlock& header_set, + SpdyString* output) { + std::unique_ptr<HpackEncoder::ProgressiveEncoder> encoderator = + encoder->EncodeHeaderSet(header_set); + SpdyString output_buffer; + http2::test::Http2Random random; + encoderator->Next(random.UniformInRange(0, 16), &output_buffer); + while (encoderator->HasNext()) { + SpdyString second_buffer; + encoderator->Next(random.UniformInRange(0, 16), &second_buffer); + output_buffer.append(second_buffer); + } + *output = std::move(output_buffer); + return true; + } + + private: + HpackEncoder* encoder_; +}; + +} // namespace test + +namespace { + +using testing::ElementsAre; +using testing::Pair; + +class HpackEncoderTest : public ::testing::TestWithParam<bool> { + protected: + typedef test::HpackEncoderPeer::Representations Representations; + + HpackEncoderTest() + : encoder_(ObtainHpackHuffmanTable()), + peer_(&encoder_), + static_(peer_.table()->GetByIndex(1)), + headers_storage_(1024 /* block size */) {} + + void SetUp() override { + use_incremental_ = GetParam(); + + // Populate dynamic entries into the table fixture. For simplicity each + // entry has name.size() + value.size() == 10. + key_1_ = peer_.table()->TryAddEntry("key1", "value1"); + key_2_ = peer_.table()->TryAddEntry("key2", "value2"); + cookie_a_ = peer_.table()->TryAddEntry("cookie", "a=bb"); + cookie_c_ = peer_.table()->TryAddEntry("cookie", "c=dd"); + + // No further insertions may occur without evictions. + peer_.table()->SetMaxSize(peer_.table()->size()); + } + + void SaveHeaders(SpdyStringPiece name, SpdyStringPiece value) { + SpdyStringPiece n(headers_storage_.Memdup(name.data(), name.size()), + name.size()); + SpdyStringPiece v(headers_storage_.Memdup(value.data(), value.size()), + value.size()); + headers_observed_.push_back(std::make_pair(n, v)); + } + + void ExpectIndex(size_t index) { + expected_.AppendPrefix(kIndexedOpcode); + expected_.AppendUint32(index); + } + void ExpectIndexedLiteral(const HpackEntry* key_entry, + SpdyStringPiece value) { + expected_.AppendPrefix(kLiteralIncrementalIndexOpcode); + expected_.AppendUint32(IndexOf(key_entry)); + ExpectString(&expected_, value); + } + void ExpectIndexedLiteral(SpdyStringPiece name, SpdyStringPiece value) { + expected_.AppendPrefix(kLiteralIncrementalIndexOpcode); + expected_.AppendUint32(0); + ExpectString(&expected_, name); + ExpectString(&expected_, value); + } + void ExpectNonIndexedLiteral(SpdyStringPiece name, SpdyStringPiece value) { + expected_.AppendPrefix(kLiteralNoIndexOpcode); + expected_.AppendUint32(0); + ExpectString(&expected_, name); + ExpectString(&expected_, value); + } + void ExpectString(HpackOutputStream* stream, SpdyStringPiece str) { + const HpackHuffmanTable& huffman_table = peer_.huffman_table(); + size_t encoded_size = peer_.compression_enabled() + ? huffman_table.EncodedSize(str) + : str.size(); + if (encoded_size < str.size()) { + expected_.AppendPrefix(kStringLiteralHuffmanEncoded); + expected_.AppendUint32(encoded_size); + huffman_table.EncodeString(str, stream); + } else { + expected_.AppendPrefix(kStringLiteralIdentityEncoded); + expected_.AppendUint32(str.size()); + expected_.AppendBytes(str); + } + } + void ExpectHeaderTableSizeUpdate(uint32_t size) { + expected_.AppendPrefix(kHeaderTableSizeUpdateOpcode); + expected_.AppendUint32(size); + } + void CompareWithExpectedEncoding(const SpdyHeaderBlock& header_set) { + SpdyString expected_out, actual_out; + expected_.TakeString(&expected_out); + EXPECT_TRUE(test::HpackEncoderPeer::EncodeHeaderSet( + &encoder_, header_set, &actual_out, use_incremental_)); + EXPECT_EQ(expected_out, actual_out); + } + size_t IndexOf(const HpackEntry* entry) { + return peer_.table()->IndexOf(entry); + } + + HpackEncoder encoder_; + test::HpackEncoderPeer peer_; + + const HpackEntry* static_; + const HpackEntry* key_1_; + const HpackEntry* key_2_; + const HpackEntry* cookie_a_; + const HpackEntry* cookie_c_; + + SpdyUnsafeArena headers_storage_; + std::vector<std::pair<SpdyStringPiece, SpdyStringPiece>> headers_observed_; + + HpackOutputStream expected_; + bool use_incremental_; +}; + +INSTANTIATE_TEST_CASE_P(HpackEncoderTests, HpackEncoderTest, ::testing::Bool()); + +TEST_P(HpackEncoderTest, SingleDynamicIndex) { + encoder_.SetHeaderListener( + [this](SpdyStringPiece name, SpdyStringPiece value) { + this->SaveHeaders(name, value); + }); + + ExpectIndex(IndexOf(key_2_)); + + SpdyHeaderBlock headers; + headers[key_2_->name()] = key_2_->value(); + CompareWithExpectedEncoding(headers); + EXPECT_THAT(headers_observed_, + ElementsAre(Pair(key_2_->name(), key_2_->value()))); +} + +TEST_P(HpackEncoderTest, SingleStaticIndex) { + ExpectIndex(IndexOf(static_)); + + SpdyHeaderBlock headers; + headers[static_->name()] = static_->value(); + CompareWithExpectedEncoding(headers); +} + +TEST_P(HpackEncoderTest, SingleStaticIndexTooLarge) { + peer_.table()->SetMaxSize(1); // Also evicts all fixtures. + ExpectIndex(IndexOf(static_)); + + SpdyHeaderBlock headers; + headers[static_->name()] = static_->value(); + CompareWithExpectedEncoding(headers); + + EXPECT_EQ(0u, peer_.table_peer().dynamic_entries()->size()); +} + +TEST_P(HpackEncoderTest, SingleLiteralWithIndexName) { + ExpectIndexedLiteral(key_2_, "value3"); + + SpdyHeaderBlock headers; + headers[key_2_->name()] = "value3"; + CompareWithExpectedEncoding(headers); + + // A new entry was inserted and added to the reference set. + HpackEntry* new_entry = &peer_.table_peer().dynamic_entries()->front(); + EXPECT_EQ(new_entry->name(), key_2_->name()); + EXPECT_EQ(new_entry->value(), "value3"); +} + +TEST_P(HpackEncoderTest, SingleLiteralWithLiteralName) { + ExpectIndexedLiteral("key3", "value3"); + + SpdyHeaderBlock headers; + headers["key3"] = "value3"; + CompareWithExpectedEncoding(headers); + + HpackEntry* new_entry = &peer_.table_peer().dynamic_entries()->front(); + EXPECT_EQ(new_entry->name(), "key3"); + EXPECT_EQ(new_entry->value(), "value3"); +} + +TEST_P(HpackEncoderTest, SingleLiteralTooLarge) { + peer_.table()->SetMaxSize(1); // Also evicts all fixtures. + + ExpectIndexedLiteral("key3", "value3"); + + // A header overflowing the header table is still emitted. + // The header table is empty. + SpdyHeaderBlock headers; + headers["key3"] = "value3"; + CompareWithExpectedEncoding(headers); + + EXPECT_EQ(0u, peer_.table_peer().dynamic_entries()->size()); +} + +TEST_P(HpackEncoderTest, EmitThanEvict) { + // |key_1_| is toggled and placed into the reference set, + // and then immediately evicted by "key3". + ExpectIndex(IndexOf(key_1_)); + ExpectIndexedLiteral("key3", "value3"); + + SpdyHeaderBlock headers; + headers[key_1_->name()] = key_1_->value(); + headers["key3"] = "value3"; + CompareWithExpectedEncoding(headers); +} + +TEST_P(HpackEncoderTest, CookieHeaderIsCrumbled) { + ExpectIndex(IndexOf(cookie_a_)); + ExpectIndex(IndexOf(cookie_c_)); + ExpectIndexedLiteral(peer_.table()->GetByName("cookie"), "e=ff"); + + SpdyHeaderBlock headers; + headers["cookie"] = "a=bb; c=dd; e=ff"; + CompareWithExpectedEncoding(headers); +} + +TEST_P(HpackEncoderTest, StringsDynamicallySelectHuffmanCoding) { + // Compactable string. Uses Huffman coding. + peer_.EmitString("feedbeef"); + expected_.AppendPrefix(kStringLiteralHuffmanEncoded); + expected_.AppendUint32(6); + expected_.AppendBytes("\x94\xA5\x92\x32\x96_"); + + // Non-compactable. Uses identity coding. + peer_.EmitString("@@@@@@"); + expected_.AppendPrefix(kStringLiteralIdentityEncoded); + expected_.AppendUint32(6); + expected_.AppendBytes("@@@@@@"); + + SpdyString expected_out, actual_out; + expected_.TakeString(&expected_out); + peer_.TakeString(&actual_out); + EXPECT_EQ(expected_out, actual_out); +} + +TEST_P(HpackEncoderTest, EncodingWithoutCompression) { + encoder_.SetHeaderListener( + [this](SpdyStringPiece name, SpdyStringPiece value) { + this->SaveHeaders(name, value); + }); + encoder_.DisableCompression(); + + ExpectNonIndexedLiteral(":path", "/index.html"); + ExpectNonIndexedLiteral("cookie", "foo=bar"); + ExpectNonIndexedLiteral("cookie", "baz=bing"); + ExpectNonIndexedLiteral("hello", "goodbye"); + + SpdyHeaderBlock headers; + headers[":path"] = "/index.html"; + headers["cookie"] = "foo=bar; baz=bing"; + headers["hello"] = "goodbye"; + + CompareWithExpectedEncoding(headers); + + EXPECT_THAT( + headers_observed_, + ElementsAre(Pair(":path", "/index.html"), Pair("cookie", "foo=bar"), + Pair("cookie", "baz=bing"), Pair("hello", "goodbye"))); +} + +TEST_P(HpackEncoderTest, MultipleEncodingPasses) { + encoder_.SetHeaderListener( + [this](SpdyStringPiece name, SpdyStringPiece value) { + this->SaveHeaders(name, value); + }); + + // Pass 1. + { + SpdyHeaderBlock headers; + headers["key1"] = "value1"; + headers["cookie"] = "a=bb"; + + ExpectIndex(IndexOf(key_1_)); + ExpectIndex(IndexOf(cookie_a_)); + CompareWithExpectedEncoding(headers); + } + // Header table is: + // 65: key1: value1 + // 64: key2: value2 + // 63: cookie: a=bb + // 62: cookie: c=dd + // Pass 2. + { + SpdyHeaderBlock headers; + headers["key2"] = "value2"; + headers["cookie"] = "c=dd; e=ff"; + + // "key2: value2" + ExpectIndex(64); + // "cookie: c=dd" + ExpectIndex(62); + // This cookie evicts |key1| from the dynamic table. + ExpectIndexedLiteral(peer_.table()->GetByName("cookie"), "e=ff"); + + CompareWithExpectedEncoding(headers); + } + // Header table is: + // 65: key2: value2 + // 64: cookie: a=bb + // 63: cookie: c=dd + // 62: cookie: e=ff + // Pass 3. + { + SpdyHeaderBlock headers; + headers["key2"] = "value2"; + headers["cookie"] = "a=bb; b=cc; c=dd"; + + // "key2: value2" + ExpectIndex(65); + // "cookie: a=bb" + ExpectIndex(64); + // This cookie evicts |key2| from the dynamic table. + ExpectIndexedLiteral(peer_.table()->GetByName("cookie"), "b=cc"); + // "cookie: c=dd" + ExpectIndex(64); + + CompareWithExpectedEncoding(headers); + } + + // clang-format off + EXPECT_THAT(headers_observed_, + ElementsAre(Pair("key1", "value1"), + Pair("cookie", "a=bb"), + Pair("key2", "value2"), + Pair("cookie", "c=dd"), + Pair("cookie", "e=ff"), + Pair("key2", "value2"), + Pair("cookie", "a=bb"), + Pair("cookie", "b=cc"), + Pair("cookie", "c=dd"))); + // clang-format on +} + +TEST_P(HpackEncoderTest, PseudoHeadersFirst) { + SpdyHeaderBlock headers; + // A pseudo-header that should not be indexed. + headers[":path"] = "/spam/eggs.html"; + // A pseudo-header to be indexed. + headers[":authority"] = "www.example.com"; + // A regular header which precedes ":" alphabetically, should still be encoded + // after pseudo-headers. + headers["-foo"] = "bar"; + headers["foo"] = "bar"; + headers["cookie"] = "c=dd"; + + // Headers are indexed in the order in which they were added. + // This entry pushes "cookie: a=bb" back to 63. + ExpectNonIndexedLiteral(":path", "/spam/eggs.html"); + ExpectIndexedLiteral(peer_.table()->GetByName(":authority"), + "www.example.com"); + ExpectIndexedLiteral("-foo", "bar"); + ExpectIndexedLiteral("foo", "bar"); + ExpectIndexedLiteral(peer_.table()->GetByName("cookie"), "c=dd"); + CompareWithExpectedEncoding(headers); +} + +TEST_P(HpackEncoderTest, CookieToCrumbs) { + test::HpackEncoderPeer peer(nullptr); + std::vector<SpdyStringPiece> out; + + // Leading and trailing whitespace is consumed. A space after ';' is consumed. + // All other spaces remain. ';' at beginning and end of string produce empty + // crumbs. + // See section 8.1.3.4 "Compressing the Cookie Header Field" in the HTTP/2 + // specification at http://tools.ietf.org/html/draft-ietf-httpbis-http2-11 + peer.CookieToCrumbs(" foo=1;bar=2 ; bar=3; bing=4; ", &out); + EXPECT_THAT(out, ElementsAre("foo=1", "bar=2 ", "bar=3", " bing=4", "")); + + peer.CookieToCrumbs(";;foo = bar ;; ;baz =bing", &out); + EXPECT_THAT(out, ElementsAre("", "", "foo = bar ", "", "", "baz =bing")); + + peer.CookieToCrumbs("baz=bing; foo=bar; baz=bing", &out); + EXPECT_THAT(out, ElementsAre("baz=bing", "foo=bar", "baz=bing")); + + peer.CookieToCrumbs("baz=bing", &out); + EXPECT_THAT(out, ElementsAre("baz=bing")); + + peer.CookieToCrumbs("", &out); + EXPECT_THAT(out, ElementsAre("")); + + peer.CookieToCrumbs("foo;bar; baz;baz;bing;", &out); + EXPECT_THAT(out, ElementsAre("foo", "bar", "baz", "baz", "bing", "")); + + peer.CookieToCrumbs(" \t foo=1;bar=2 ; bar=3;\t ", &out); + EXPECT_THAT(out, ElementsAre("foo=1", "bar=2 ", "bar=3", "")); + + peer.CookieToCrumbs(" \t foo=1;bar=2 ; bar=3 \t ", &out); + EXPECT_THAT(out, ElementsAre("foo=1", "bar=2 ", "bar=3")); +} + +TEST_P(HpackEncoderTest, DecomposeRepresentation) { + test::HpackEncoderPeer peer(nullptr); + std::vector<SpdyStringPiece> out; + + peer.DecomposeRepresentation("", &out); + EXPECT_THAT(out, ElementsAre("")); + + peer.DecomposeRepresentation("foobar", &out); + EXPECT_THAT(out, ElementsAre("foobar")); + + peer.DecomposeRepresentation(SpdyStringPiece("foo\0bar", 7), &out); + EXPECT_THAT(out, ElementsAre("foo", "bar")); + + peer.DecomposeRepresentation(SpdyStringPiece("\0foo\0bar", 8), &out); + EXPECT_THAT(out, ElementsAre("", "foo", "bar")); + + peer.DecomposeRepresentation(SpdyStringPiece("foo\0bar\0", 8), &out); + EXPECT_THAT(out, ElementsAre("foo", "bar", "")); + + peer.DecomposeRepresentation(SpdyStringPiece("\0foo\0bar\0", 9), &out); + EXPECT_THAT(out, ElementsAre("", "foo", "bar", "")); +} + +// Test that encoded headers do not have \0-delimited multiple values, as this +// became disallowed in HTTP/2 draft-14. +TEST_P(HpackEncoderTest, CrumbleNullByteDelimitedValue) { + SpdyHeaderBlock headers; + // A header field to be crumbled: "spam: foo\0bar". + headers["spam"] = SpdyString("foo\0bar", 7); + + ExpectIndexedLiteral("spam", "foo"); + expected_.AppendPrefix(kLiteralIncrementalIndexOpcode); + expected_.AppendUint32(62); + expected_.AppendPrefix(kStringLiteralIdentityEncoded); + expected_.AppendUint32(3); + expected_.AppendBytes("bar"); + CompareWithExpectedEncoding(headers); +} + +TEST_P(HpackEncoderTest, HeaderTableSizeUpdate) { + encoder_.ApplyHeaderTableSizeSetting(1024); + ExpectHeaderTableSizeUpdate(1024); + ExpectIndexedLiteral("key3", "value3"); + + SpdyHeaderBlock headers; + headers["key3"] = "value3"; + CompareWithExpectedEncoding(headers); + + HpackEntry* new_entry = &peer_.table_peer().dynamic_entries()->front(); + EXPECT_EQ(new_entry->name(), "key3"); + EXPECT_EQ(new_entry->value(), "value3"); +} + +TEST_P(HpackEncoderTest, HeaderTableSizeUpdateWithMin) { + const size_t starting_size = peer_.table()->settings_size_bound(); + encoder_.ApplyHeaderTableSizeSetting(starting_size - 2); + encoder_.ApplyHeaderTableSizeSetting(starting_size - 1); + // We must encode the low watermark, so the peer knows to evict entries + // if necessary. + ExpectHeaderTableSizeUpdate(starting_size - 2); + ExpectHeaderTableSizeUpdate(starting_size - 1); + ExpectIndexedLiteral("key3", "value3"); + + SpdyHeaderBlock headers; + headers["key3"] = "value3"; + CompareWithExpectedEncoding(headers); + + HpackEntry* new_entry = &peer_.table_peer().dynamic_entries()->front(); + EXPECT_EQ(new_entry->name(), "key3"); + EXPECT_EQ(new_entry->value(), "value3"); +} + +TEST_P(HpackEncoderTest, HeaderTableSizeUpdateWithExistingSize) { + encoder_.ApplyHeaderTableSizeSetting(peer_.table()->settings_size_bound()); + // No encoded size update. + ExpectIndexedLiteral("key3", "value3"); + + SpdyHeaderBlock headers; + headers["key3"] = "value3"; + CompareWithExpectedEncoding(headers); + + HpackEntry* new_entry = &peer_.table_peer().dynamic_entries()->front(); + EXPECT_EQ(new_entry->name(), "key3"); + EXPECT_EQ(new_entry->value(), "value3"); +} + +TEST_P(HpackEncoderTest, HeaderTableSizeUpdatesWithGreaterSize) { + const size_t starting_size = peer_.table()->settings_size_bound(); + encoder_.ApplyHeaderTableSizeSetting(starting_size + 1); + encoder_.ApplyHeaderTableSizeSetting(starting_size + 2); + // Only a single size update to the final size. + ExpectHeaderTableSizeUpdate(starting_size + 2); + ExpectIndexedLiteral("key3", "value3"); + + SpdyHeaderBlock headers; + headers["key3"] = "value3"; + CompareWithExpectedEncoding(headers); + + HpackEntry* new_entry = &peer_.table_peer().dynamic_entries()->front(); + EXPECT_EQ(new_entry->name(), "key3"); + EXPECT_EQ(new_entry->value(), "value3"); +} + +} // namespace + +} // namespace spdy
diff --git a/spdy/core/hpack/hpack_entry.cc b/spdy/core/hpack/hpack_entry.cc new file mode 100644 index 0000000..90d53e6 --- /dev/null +++ b/spdy/core/hpack/hpack_entry.cc
@@ -0,0 +1,89 @@ +// Copyright 2014 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_entry.h" + +#include "base/logging.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_estimate_memory_usage.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_string_utils.h" + +namespace spdy { + +const size_t HpackEntry::kSizeOverhead = 32; + +HpackEntry::HpackEntry(SpdyStringPiece name, + SpdyStringPiece value, + bool is_static, + size_t insertion_index) + : name_(name.data(), name.size()), + value_(value.data(), value.size()), + name_ref_(name_), + value_ref_(value_), + insertion_index_(insertion_index), + type_(is_static ? STATIC : DYNAMIC), + time_added_(0) {} + +HpackEntry::HpackEntry(SpdyStringPiece name, SpdyStringPiece value) + : name_ref_(name), + value_ref_(value), + insertion_index_(0), + type_(LOOKUP), + time_added_(0) {} + +HpackEntry::HpackEntry() : insertion_index_(0), type_(LOOKUP), time_added_(0) {} + +HpackEntry::HpackEntry(const HpackEntry& other) + : insertion_index_(other.insertion_index_), + type_(other.type_), + time_added_(0) { + if (type_ == LOOKUP) { + name_ref_ = other.name_ref_; + value_ref_ = other.value_ref_; + } else { + name_ = other.name_; + value_ = other.value_; + name_ref_ = SpdyStringPiece(name_.data(), name_.size()); + value_ref_ = SpdyStringPiece(value_.data(), value_.size()); + } +} + +HpackEntry& HpackEntry::operator=(const HpackEntry& other) { + insertion_index_ = other.insertion_index_; + type_ = other.type_; + if (type_ == LOOKUP) { + name_.clear(); + value_.clear(); + name_ref_ = other.name_ref_; + value_ref_ = other.value_ref_; + return *this; + } + name_ = other.name_; + value_ = other.value_; + name_ref_ = SpdyStringPiece(name_.data(), name_.size()); + value_ref_ = SpdyStringPiece(value_.data(), value_.size()); + return *this; +} + +HpackEntry::~HpackEntry() = default; + +// static +size_t HpackEntry::Size(SpdyStringPiece name, SpdyStringPiece value) { + return name.size() + value.size() + kSizeOverhead; +} +size_t HpackEntry::Size() const { + return Size(name(), value()); +} + +SpdyString HpackEntry::GetDebugString() const { + return SpdyStrCat( + "{ name: \"", name_ref_, "\", value: \"", value_ref_, + "\", index: ", insertion_index_, " ", + (IsStatic() ? " static" : (IsLookup() ? " lookup" : " dynamic")), " }"); +} + +size_t HpackEntry::EstimateMemoryUsage() const { + return SpdyEstimateMemoryUsage(name_) + SpdyEstimateMemoryUsage(value_); +} + +} // namespace spdy
diff --git a/spdy/core/hpack/hpack_entry.h b/spdy/core/hpack/hpack_entry.h new file mode 100644 index 0000000..28dee47 --- /dev/null +++ b/spdy/core/hpack/hpack_entry.h
@@ -0,0 +1,110 @@ +// Copyright 2014 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#ifndef QUICHE_SPDY_CORE_HPACK_HPACK_ENTRY_H_ +#define QUICHE_SPDY_CORE_HPACK_HPACK_ENTRY_H_ + +#include <cstddef> +#include <cstdint> + +#include "base/macros.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_export.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_string.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_string_piece.h" + +// All section references below are to +// http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-08 + +namespace spdy { + +// A structure for an entry in the static table (3.3.1) +// and the header table (3.3.2). +class SPDY_EXPORT_PRIVATE HpackEntry { + public: + // The constant amount added to name().size() and value().size() to + // get the size of an HpackEntry as defined in 5.1. + static const size_t kSizeOverhead; + + // Creates an entry. Preconditions: + // - |is_static| captures whether this entry is a member of the static + // or dynamic header table. + // - |insertion_index| is this entry's index in the total set of entries ever + // inserted into the header table (including static entries). + // + // The combination of |is_static| and |insertion_index| allows an + // HpackEntryTable to determine the index of an HpackEntry in O(1) time. + // Copies |name| and |value|. + HpackEntry(SpdyStringPiece name, + SpdyStringPiece value, + bool is_static, + size_t insertion_index); + + // Create a 'lookup' entry (only) suitable for querying a HpackEntrySet. The + // instance InsertionIndex() always returns 0 and IsLookup() returns true. + // The memory backing |name| and |value| must outlive this object. + HpackEntry(SpdyStringPiece name, SpdyStringPiece value); + + HpackEntry(const HpackEntry& other); + HpackEntry& operator=(const HpackEntry& other); + + // Creates an entry with empty name and value. Only defined so that + // entries can be stored in STL containers. + HpackEntry(); + + ~HpackEntry(); + + SpdyStringPiece name() const { return name_ref_; } + SpdyStringPiece value() const { return value_ref_; } + + // Returns whether this entry is a member of the static (as opposed to + // dynamic) table. + bool IsStatic() const { return type_ == STATIC; } + + // Returns whether this entry is a lookup-only entry. + bool IsLookup() const { return type_ == LOOKUP; } + + // Used to compute the entry's index in the header table. + size_t InsertionIndex() const { return insertion_index_; } + + // Returns the size of an entry as defined in 5.1. + static size_t Size(SpdyStringPiece name, SpdyStringPiece value); + size_t Size() const; + + SpdyString GetDebugString() const; + + int64_t time_added() const { return time_added_; } + void set_time_added(int64_t now) { time_added_ = now; } + + // Returns the estimate of dynamically allocated memory in bytes. + size_t EstimateMemoryUsage() const; + + private: + enum EntryType { + LOOKUP, + DYNAMIC, + STATIC, + }; + + // These members are not used for LOOKUP entries. + SpdyString name_; + SpdyString value_; + + // These members are always valid. For DYNAMIC and STATIC entries, they + // always point to |name_| and |value_|. + SpdyStringPiece name_ref_; + SpdyStringPiece value_ref_; + + // The entry's index in the total set of entries ever inserted into the header + // table. + size_t insertion_index_; + + EntryType type_; + + // For HpackHeaderTable::DebugVisitorInterface + int64_t time_added_; +}; + +} // namespace spdy + +#endif // QUICHE_SPDY_CORE_HPACK_HPACK_ENTRY_H_
diff --git a/spdy/core/hpack/hpack_entry_test.cc b/spdy/core/hpack/hpack_entry_test.cc new file mode 100644 index 0000000..507c851 --- /dev/null +++ b/spdy/core/hpack/hpack_entry_test.cc
@@ -0,0 +1,122 @@ +// Copyright 2014 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_entry.h" + +#include "testing/gtest/include/gtest/gtest.h" + +namespace spdy { + +namespace { + +class HpackEntryTest : public ::testing::Test { + protected: + HpackEntryTest() + : name_("header-name"), + value_("header value"), + total_insertions_(0), + table_size_(0) {} + + // These builders maintain the same external table invariants that a "real" + // table (ie HpackHeaderTable) would. + HpackEntry StaticEntry() { + return HpackEntry(name_, value_, true, total_insertions_++); + } + HpackEntry DynamicEntry() { + ++table_size_; + size_t index = total_insertions_++; + return HpackEntry(name_, value_, false, index); + } + void DropEntry() { --table_size_; } + + size_t IndexOf(const HpackEntry& entry) const { + if (entry.IsStatic()) { + return 1 + entry.InsertionIndex() + table_size_; + } else { + return total_insertions_ - entry.InsertionIndex(); + } + } + + size_t Size() { + return name_.size() + value_.size() + HpackEntry::kSizeOverhead; + } + + SpdyString name_, value_; + + private: + // Referenced by HpackEntry instances. + size_t total_insertions_; + size_t table_size_; +}; + +TEST_F(HpackEntryTest, StaticConstructor) { + HpackEntry entry(StaticEntry()); + + EXPECT_EQ(name_, entry.name()); + EXPECT_EQ(value_, entry.value()); + EXPECT_TRUE(entry.IsStatic()); + EXPECT_EQ(1u, IndexOf(entry)); + EXPECT_EQ(Size(), entry.Size()); +} + +TEST_F(HpackEntryTest, DynamicConstructor) { + HpackEntry entry(DynamicEntry()); + + EXPECT_EQ(name_, entry.name()); + EXPECT_EQ(value_, entry.value()); + EXPECT_FALSE(entry.IsStatic()); + EXPECT_EQ(1u, IndexOf(entry)); + EXPECT_EQ(Size(), entry.Size()); +} + +TEST_F(HpackEntryTest, LookupConstructor) { + HpackEntry entry(name_, value_); + + EXPECT_EQ(name_, entry.name()); + EXPECT_EQ(value_, entry.value()); + EXPECT_FALSE(entry.IsStatic()); + EXPECT_EQ(0u, IndexOf(entry)); + EXPECT_EQ(Size(), entry.Size()); +} + +TEST_F(HpackEntryTest, DefaultConstructor) { + HpackEntry entry; + + EXPECT_TRUE(entry.name().empty()); + EXPECT_TRUE(entry.value().empty()); + EXPECT_EQ(HpackEntry::kSizeOverhead, entry.Size()); +} + +TEST_F(HpackEntryTest, IndexUpdate) { + HpackEntry static1(StaticEntry()); + HpackEntry static2(StaticEntry()); + + EXPECT_EQ(1u, IndexOf(static1)); + EXPECT_EQ(2u, IndexOf(static2)); + + HpackEntry dynamic1(DynamicEntry()); + HpackEntry dynamic2(DynamicEntry()); + + EXPECT_EQ(1u, IndexOf(dynamic2)); + EXPECT_EQ(2u, IndexOf(dynamic1)); + EXPECT_EQ(3u, IndexOf(static1)); + EXPECT_EQ(4u, IndexOf(static2)); + + DropEntry(); // Drops |dynamic1|. + + EXPECT_EQ(1u, IndexOf(dynamic2)); + EXPECT_EQ(2u, IndexOf(static1)); + EXPECT_EQ(3u, IndexOf(static2)); + + HpackEntry dynamic3(DynamicEntry()); + + EXPECT_EQ(1u, IndexOf(dynamic3)); + EXPECT_EQ(2u, IndexOf(dynamic2)); + EXPECT_EQ(3u, IndexOf(static1)); + EXPECT_EQ(4u, IndexOf(static2)); +} + +} // namespace + +} // namespace spdy
diff --git a/spdy/core/hpack/hpack_header_table.cc b/spdy/core/hpack/hpack_header_table.cc new file mode 100644 index 0000000..dbe565f --- /dev/null +++ b/spdy/core/hpack/hpack_header_table.cc
@@ -0,0 +1,274 @@ +// Copyright 2014 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_header_table.h" + +#include <algorithm> + +#include "base/logging.h" +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_constants.h" +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_static_table.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_containers.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_estimate_memory_usage.h" + +namespace spdy { + +size_t HpackHeaderTable::EntryHasher::operator()( + const HpackEntry* entry) const { + return SpdyHashStringPair(entry->name(), entry->value()); +} + +bool HpackHeaderTable::EntriesEq::operator()(const HpackEntry* lhs, + const HpackEntry* rhs) const { + if (lhs == nullptr) { + return rhs == nullptr; + } + if (rhs == nullptr) { + return false; + } + return lhs->name() == rhs->name() && lhs->value() == rhs->value(); +} + +HpackHeaderTable::HpackHeaderTable() + : static_entries_(ObtainHpackStaticTable().GetStaticEntries()), + static_index_(ObtainHpackStaticTable().GetStaticIndex()), + static_name_index_(ObtainHpackStaticTable().GetStaticNameIndex()), + settings_size_bound_(kDefaultHeaderTableSizeSetting), + size_(0), + max_size_(kDefaultHeaderTableSizeSetting), + total_insertions_(static_entries_.size()) {} + +HpackHeaderTable::~HpackHeaderTable() = default; + +const HpackEntry* HpackHeaderTable::GetByIndex(size_t index) { + if (index == 0) { + return nullptr; + } + index -= 1; + if (index < static_entries_.size()) { + return &static_entries_[index]; + } + index -= static_entries_.size(); + if (index < dynamic_entries_.size()) { + const HpackEntry* result = &dynamic_entries_[index]; + if (debug_visitor_ != nullptr) { + debug_visitor_->OnUseEntry(*result); + } + return result; + } + return nullptr; +} + +const HpackEntry* HpackHeaderTable::GetByName(SpdyStringPiece name) { + { + auto it = static_name_index_.find(name); + if (it != static_name_index_.end()) { + return it->second; + } + } + { + NameToEntryMap::const_iterator it = dynamic_name_index_.find(name); + if (it != dynamic_name_index_.end()) { + const HpackEntry* result = it->second; + if (debug_visitor_ != nullptr) { + debug_visitor_->OnUseEntry(*result); + } + return result; + } + } + return nullptr; +} + +const HpackEntry* HpackHeaderTable::GetByNameAndValue(SpdyStringPiece name, + SpdyStringPiece value) { + HpackEntry query(name, value); + { + auto it = static_index_.find(&query); + if (it != static_index_.end()) { + return *it; + } + } + { + auto it = dynamic_index_.find(&query); + if (it != dynamic_index_.end()) { + const HpackEntry* result = *it; + if (debug_visitor_ != nullptr) { + debug_visitor_->OnUseEntry(*result); + } + return result; + } + } + return nullptr; +} + +size_t HpackHeaderTable::IndexOf(const HpackEntry* entry) const { + if (entry->IsLookup()) { + return 0; + } else if (entry->IsStatic()) { + return 1 + entry->InsertionIndex(); + } else { + return total_insertions_ - entry->InsertionIndex() + static_entries_.size(); + } +} + +void HpackHeaderTable::SetMaxSize(size_t max_size) { + CHECK_LE(max_size, settings_size_bound_); + + max_size_ = max_size; + if (size_ > max_size_) { + Evict(EvictionCountToReclaim(size_ - max_size_)); + CHECK_LE(size_, max_size_); + } +} + +void HpackHeaderTable::SetSettingsHeaderTableSize(size_t settings_size) { + settings_size_bound_ = settings_size; + SetMaxSize(settings_size_bound_); +} + +void HpackHeaderTable::EvictionSet(SpdyStringPiece name, + SpdyStringPiece value, + EntryTable::iterator* begin_out, + EntryTable::iterator* end_out) { + size_t eviction_count = EvictionCountForEntry(name, value); + *begin_out = dynamic_entries_.end() - eviction_count; + *end_out = dynamic_entries_.end(); +} + +size_t HpackHeaderTable::EvictionCountForEntry(SpdyStringPiece name, + SpdyStringPiece value) const { + size_t available_size = max_size_ - size_; + size_t entry_size = HpackEntry::Size(name, value); + + if (entry_size <= available_size) { + // No evictions are required. + return 0; + } + return EvictionCountToReclaim(entry_size - available_size); +} + +size_t HpackHeaderTable::EvictionCountToReclaim(size_t reclaim_size) const { + size_t count = 0; + for (auto it = dynamic_entries_.rbegin(); + it != dynamic_entries_.rend() && reclaim_size != 0; ++it, ++count) { + reclaim_size -= std::min(reclaim_size, it->Size()); + } + return count; +} + +void HpackHeaderTable::Evict(size_t count) { + for (size_t i = 0; i != count; ++i) { + CHECK(!dynamic_entries_.empty()); + HpackEntry* entry = &dynamic_entries_.back(); + + size_ -= entry->Size(); + auto it = dynamic_index_.find(entry); + DCHECK(it != dynamic_index_.end()); + // Only remove an entry from the index if its insertion index matches; + // otherwise, the index refers to another entry with the same name and + // value. + if ((*it)->InsertionIndex() == entry->InsertionIndex()) { + dynamic_index_.erase(it); + } + auto name_it = dynamic_name_index_.find(entry->name()); + DCHECK(name_it != dynamic_name_index_.end()); + // Only remove an entry from the literal index if its insertion index + /// matches; otherwise, the index refers to another entry with the same + // name. + if (name_it->second->InsertionIndex() == entry->InsertionIndex()) { + dynamic_name_index_.erase(name_it); + } + dynamic_entries_.pop_back(); + } +} + +const HpackEntry* HpackHeaderTable::TryAddEntry(SpdyStringPiece name, + SpdyStringPiece value) { + Evict(EvictionCountForEntry(name, value)); + + size_t entry_size = HpackEntry::Size(name, value); + if (entry_size > (max_size_ - size_)) { + // Entire table has been emptied, but there's still insufficient room. + DCHECK(dynamic_entries_.empty()); + DCHECK_EQ(0u, size_); + return nullptr; + } + dynamic_entries_.push_front(HpackEntry(name, value, + false, // is_static + total_insertions_)); + HpackEntry* new_entry = &dynamic_entries_.front(); + auto index_result = dynamic_index_.insert(new_entry); + if (!index_result.second) { + // An entry with the same name and value already exists in the dynamic + // index. We should replace it with the newly added entry. + DVLOG(1) << "Found existing entry: " + << (*index_result.first)->GetDebugString() + << " replacing with: " << new_entry->GetDebugString(); + DCHECK_GT(new_entry->InsertionIndex(), + (*index_result.first)->InsertionIndex()); + dynamic_index_.erase(index_result.first); + CHECK(dynamic_index_.insert(new_entry).second); + } + + auto name_result = + dynamic_name_index_.insert(std::make_pair(new_entry->name(), new_entry)); + if (!name_result.second) { + // An entry with the same name already exists in the dynamic index. We + // should replace it with the newly added entry. + DVLOG(1) << "Found existing entry: " + << name_result.first->second->GetDebugString() + << " replacing with: " << new_entry->GetDebugString(); + DCHECK_GT(new_entry->InsertionIndex(), + name_result.first->second->InsertionIndex()); + dynamic_name_index_.erase(name_result.first); + auto insert_result = dynamic_name_index_.insert( + std::make_pair(new_entry->name(), new_entry)); + CHECK(insert_result.second); + } + + size_ += entry_size; + ++total_insertions_; + if (debug_visitor_ != nullptr) { + // Call |debug_visitor_->OnNewEntry()| to get the current time. + HpackEntry& entry = dynamic_entries_.front(); + entry.set_time_added(debug_visitor_->OnNewEntry(entry)); + DVLOG(2) << "HpackHeaderTable::OnNewEntry: name=" << entry.name() + << ", value=" << entry.value() + << ", insert_index=" << entry.InsertionIndex() + << ", time_added=" << entry.time_added(); + } + + return &dynamic_entries_.front(); +} + +void HpackHeaderTable::DebugLogTableState() const { + DVLOG(2) << "Dynamic table:"; + for (auto it = dynamic_entries_.begin(); it != dynamic_entries_.end(); ++it) { + DVLOG(2) << " " << it->GetDebugString(); + } + DVLOG(2) << "Full Static Index:"; + for (const auto* entry : static_index_) { + DVLOG(2) << " " << entry->GetDebugString(); + } + DVLOG(2) << "Full Static Name Index:"; + for (const auto it : static_name_index_) { + DVLOG(2) << " " << it.first << ": " << it.second->GetDebugString(); + } + DVLOG(2) << "Full Dynamic Index:"; + for (const auto* entry : dynamic_index_) { + DVLOG(2) << " " << entry->GetDebugString(); + } + DVLOG(2) << "Full Dynamic Name Index:"; + for (const auto it : dynamic_name_index_) { + DVLOG(2) << " " << it.first << ": " << it.second->GetDebugString(); + } +} + +size_t HpackHeaderTable::EstimateMemoryUsage() const { + return SpdyEstimateMemoryUsage(dynamic_entries_) + + SpdyEstimateMemoryUsage(dynamic_index_) + + SpdyEstimateMemoryUsage(dynamic_name_index_); +} + +} // namespace spdy
diff --git a/spdy/core/hpack/hpack_header_table.h b/spdy/core/hpack/hpack_header_table.h new file mode 100644 index 0000000..e85edb7 --- /dev/null +++ b/spdy/core/hpack/hpack_header_table.h
@@ -0,0 +1,180 @@ +// Copyright 2014 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#ifndef QUICHE_SPDY_CORE_HPACK_HPACK_HEADER_TABLE_H_ +#define QUICHE_SPDY_CORE_HPACK_HPACK_HEADER_TABLE_H_ + +#include <cstddef> +#include <cstdint> +#include <deque> +#include <memory> + +#include "base/macros.h" +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_entry.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_containers.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_export.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_macros.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_string_piece.h" + +// All section references below are to http://tools.ietf.org/html/rfc7541. + +namespace spdy { + +namespace test { +class HpackHeaderTablePeer; +} // namespace test + +// A data structure for the static table (2.3.1) and the dynamic table (2.3.2). +class SPDY_EXPORT_PRIVATE HpackHeaderTable { + public: + friend class test::HpackHeaderTablePeer; + + // Debug visitor my be used to extract debug/internal information + // about the HpackHeaderTable as it operates. + // + // Most HpackHeaderTable implementations do not need to bother with + // this interface at all. + class DebugVisitorInterface { + public: + virtual ~DebugVisitorInterface() {} + + // |OnNewEntry()| and |OnUseEntry()| can be used together to + // gather data about the distribution of time intervals between + // creation and reference of entries in the dynamic table. The + // data is desired to sanity check a proposed extension to HPACK + // for QUIC that would eliminate inter-stream head of line + // blocking (due to standard HPACK). The visitor should return + // the current time from |OnNewEntry()|, which will be passed + // to |OnUseEntry()| each time that particular entry is used to + // emit an indexed representation. + virtual int64_t OnNewEntry(const HpackEntry& entry) = 0; + virtual void OnUseEntry(const HpackEntry& entry) = 0; + }; + + // HpackHeaderTable takes advantage of the deque property that references + // remain valid, so long as insertions & deletions are at the head & tail. + // This precludes the use of base::circular_deque. + // + // If this changes (we want to change to circular_deque or we start to drop + // entries from the middle of the table), this should to be a std::list, in + // which case |*_index_| can be trivially extended to map to list iterators. + using EntryTable = std::deque<HpackEntry>; + + struct SPDY_EXPORT_PRIVATE EntryHasher { + size_t operator()(const HpackEntry* entry) const; + }; + struct SPDY_EXPORT_PRIVATE EntriesEq { + bool operator()(const HpackEntry* lhs, const HpackEntry* rhs) const; + }; + using UnorderedEntrySet = SpdyHashSet<HpackEntry*, EntryHasher, EntriesEq>; + using NameToEntryMap = + SpdyHashMap<SpdyStringPiece, const HpackEntry*, SpdyStringPieceHash>; + + HpackHeaderTable(); + HpackHeaderTable(const HpackHeaderTable&) = delete; + HpackHeaderTable& operator=(const HpackHeaderTable&) = delete; + + ~HpackHeaderTable(); + + // Last-acknowledged value of SETTINGS_HEADER_TABLE_SIZE. + size_t settings_size_bound() const { return settings_size_bound_; } + + // Current and maximum estimated byte size of the table, as described in + // 4.1. Notably, this is /not/ the number of entries in the table. + size_t size() const { return size_; } + size_t max_size() const { return max_size_; } + + // Returns the entry matching the index, or NULL. + const HpackEntry* GetByIndex(size_t index); + + // Returns the lowest-value entry having |name|, or NULL. + const HpackEntry* GetByName(SpdyStringPiece name); + + // Returns the lowest-index matching entry, or NULL. + const HpackEntry* GetByNameAndValue(SpdyStringPiece name, + SpdyStringPiece value); + + // Returns the index of an entry within this header table. + size_t IndexOf(const HpackEntry* entry) const; + + // Sets the maximum size of the header table, evicting entries if + // necessary as described in 5.2. + void SetMaxSize(size_t max_size); + + // Sets the SETTINGS_HEADER_TABLE_SIZE bound of the table. Will call + // SetMaxSize() as needed to preserve max_size() <= settings_size_bound(). + void SetSettingsHeaderTableSize(size_t settings_size); + + // Determine the set of entries which would be evicted by the insertion + // of |name| & |value| into the table, as per section 4.4. No eviction + // actually occurs. The set is returned via range [begin_out, end_out). + void EvictionSet(SpdyStringPiece name, + SpdyStringPiece value, + EntryTable::iterator* begin_out, + EntryTable::iterator* end_out); + + // Adds an entry for the representation, evicting entries as needed. |name| + // and |value| must not be owned by an entry which could be evicted. The + // added HpackEntry is returned, or NULL is returned if all entries were + // evicted and the empty table is of insufficent size for the representation. + const HpackEntry* TryAddEntry(SpdyStringPiece name, SpdyStringPiece value); + + void DebugLogTableState() const SPDY_UNUSED; + + void set_debug_visitor(std::unique_ptr<DebugVisitorInterface> visitor) { + debug_visitor_ = std::move(visitor); + } + + // Returns the estimate of dynamically allocated memory in bytes. + size_t EstimateMemoryUsage() const; + + private: + // Returns number of evictions required to enter |name| & |value|. + size_t EvictionCountForEntry(SpdyStringPiece name, + SpdyStringPiece value) const; + + // Returns number of evictions required to reclaim |reclaim_size| table size. + size_t EvictionCountToReclaim(size_t reclaim_size) const; + + // Evicts |count| oldest entries from the table. + void Evict(size_t count); + + // |static_entries_|, |static_index_|, and |static_name_index_| are owned by + // HpackStaticTable singleton. + + // Tracks HpackEntries by index. + const EntryTable& static_entries_; + EntryTable dynamic_entries_; + + // Tracks the unique HpackEntry for a given header name and value. + const UnorderedEntrySet& static_index_; + + // Tracks the first static entry for each name in the static table. + const NameToEntryMap& static_name_index_; + + // Tracks the most recently inserted HpackEntry for a given header name and + // value. + UnorderedEntrySet dynamic_index_; + + // Tracks the most recently inserted HpackEntry for a given header name. + NameToEntryMap dynamic_name_index_; + + // Last acknowledged value for SETTINGS_HEADER_TABLE_SIZE. + size_t settings_size_bound_; + + // Estimated current and maximum byte size of the table. + // |max_size_| <= |settings_size_bound_| + size_t size_; + size_t max_size_; + + // Total number of table insertions which have occurred. Referenced by + // IndexOf() for determination of an HpackEntry's table index. + size_t total_insertions_; + + std::unique_ptr<DebugVisitorInterface> debug_visitor_; +}; + +} // namespace spdy + +#endif // QUICHE_SPDY_CORE_HPACK_HPACK_HEADER_TABLE_H_
diff --git a/spdy/core/hpack/hpack_header_table_test.cc b/spdy/core/hpack/hpack_header_table_test.cc new file mode 100644 index 0000000..b032aba --- /dev/null +++ b/spdy/core/hpack/hpack_header_table_test.cc
@@ -0,0 +1,446 @@ +// Copyright 2014 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_header_table.h" + +#include <algorithm> +#include <cstdint> +#include <set> +#include <vector> + +#include "base/macros.h" +#include "testing/gtest/include/gtest/gtest.h" +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_constants.h" +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_entry.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_string.h" + +namespace spdy { + +using std::distance; + +namespace test { + +class HpackHeaderTablePeer { + public: + explicit HpackHeaderTablePeer(HpackHeaderTable* table) : table_(table) {} + + const HpackHeaderTable::EntryTable& dynamic_entries() { + return table_->dynamic_entries_; + } + const HpackHeaderTable::EntryTable& static_entries() { + return table_->static_entries_; + } + size_t index_size() { + return table_->static_index_.size() + table_->dynamic_index_.size(); + } + std::vector<HpackEntry*> EvictionSet(SpdyStringPiece name, + SpdyStringPiece value) { + HpackHeaderTable::EntryTable::iterator begin, end; + table_->EvictionSet(name, value, &begin, &end); + std::vector<HpackEntry*> result; + for (; begin != end; ++begin) { + result.push_back(&(*begin)); + } + return result; + } + size_t total_insertions() { return table_->total_insertions_; } + size_t dynamic_entries_count() { return table_->dynamic_entries_.size(); } + size_t EvictionCountForEntry(SpdyStringPiece name, SpdyStringPiece value) { + return table_->EvictionCountForEntry(name, value); + } + size_t EvictionCountToReclaim(size_t reclaim_size) { + return table_->EvictionCountToReclaim(reclaim_size); + } + void Evict(size_t count) { return table_->Evict(count); } + + void AddDynamicEntry(SpdyStringPiece name, SpdyStringPiece value) { + table_->dynamic_entries_.push_back( + HpackEntry(name, value, false, table_->total_insertions_++)); + } + + private: + HpackHeaderTable* table_; +}; + +} // namespace test + +namespace { + +class HpackHeaderTableTest : public ::testing::Test { + protected: + typedef std::vector<HpackEntry> HpackEntryVector; + + HpackHeaderTableTest() : table_(), peer_(&table_) {} + + // Returns an entry whose Size() is equal to the given one. + static HpackEntry MakeEntryOfSize(uint32_t size) { + EXPECT_GE(size, HpackEntry::kSizeOverhead); + SpdyString name((size - HpackEntry::kSizeOverhead) / 2, 'n'); + SpdyString value(size - HpackEntry::kSizeOverhead - name.size(), 'v'); + HpackEntry entry(name, value, false, 0); + EXPECT_EQ(size, entry.Size()); + return entry; + } + + // Returns a vector of entries whose total size is equal to the given + // one. + static HpackEntryVector MakeEntriesOfTotalSize(uint32_t total_size) { + EXPECT_GE(total_size, HpackEntry::kSizeOverhead); + uint32_t entry_size = HpackEntry::kSizeOverhead; + uint32_t remaining_size = total_size; + HpackEntryVector entries; + while (remaining_size > 0) { + EXPECT_LE(entry_size, remaining_size); + entries.push_back(MakeEntryOfSize(entry_size)); + remaining_size -= entry_size; + entry_size = std::min(remaining_size, entry_size + 32); + } + return entries; + } + + // Adds the given vector of entries to the given header table, + // expecting no eviction to happen. + void AddEntriesExpectNoEviction(const HpackEntryVector& entries) { + for (auto it = entries.begin(); it != entries.end(); ++it) { + HpackHeaderTable::EntryTable::iterator begin, end; + + table_.EvictionSet(it->name(), it->value(), &begin, &end); + EXPECT_EQ(0, distance(begin, end)); + + const HpackEntry* entry = table_.TryAddEntry(it->name(), it->value()); + EXPECT_NE(entry, static_cast<HpackEntry*>(nullptr)); + } + + for (size_t i = 0; i != entries.size(); ++i) { + // Static table has 61 entries, dynamic entries follow those. + size_t index = 61 + entries.size() - i; + const HpackEntry* entry = table_.GetByIndex(index); + EXPECT_EQ(entries[i].name(), entry->name()); + EXPECT_EQ(entries[i].value(), entry->value()); + EXPECT_EQ(index, table_.IndexOf(entry)); + } + } + + HpackEntry DynamicEntry(const SpdyString& name, const SpdyString& value) { + peer_.AddDynamicEntry(name, value); + return peer_.dynamic_entries().back(); + } + + HpackHeaderTable table_; + test::HpackHeaderTablePeer peer_; +}; + +TEST_F(HpackHeaderTableTest, StaticTableInitialization) { + EXPECT_EQ(0u, table_.size()); + EXPECT_EQ(kDefaultHeaderTableSizeSetting, table_.max_size()); + EXPECT_EQ(kDefaultHeaderTableSizeSetting, table_.settings_size_bound()); + + EXPECT_EQ(0u, peer_.dynamic_entries_count()); + EXPECT_EQ(peer_.static_entries().size(), peer_.total_insertions()); + + // Static entries have been populated and inserted into the table & index. + EXPECT_NE(0u, peer_.static_entries().size()); + EXPECT_EQ(peer_.index_size(), peer_.static_entries().size()); + for (size_t i = 0; i != peer_.static_entries().size(); ++i) { + const HpackEntry* entry = &peer_.static_entries()[i]; + + EXPECT_TRUE(entry->IsStatic()); + EXPECT_EQ(entry, table_.GetByIndex(i + 1)); + EXPECT_EQ(entry, table_.GetByNameAndValue(entry->name(), entry->value())); + } +} + +TEST_F(HpackHeaderTableTest, BasicDynamicEntryInsertionAndEviction) { + size_t static_count = peer_.total_insertions(); + const HpackEntry* first_static_entry = table_.GetByIndex(1); + + EXPECT_EQ(1u, table_.IndexOf(first_static_entry)); + + const HpackEntry* entry = table_.TryAddEntry("header-key", "Header Value"); + EXPECT_EQ("header-key", entry->name()); + EXPECT_EQ("Header Value", entry->value()); + EXPECT_FALSE(entry->IsStatic()); + + // Table counts were updated appropriately. + EXPECT_EQ(entry->Size(), table_.size()); + EXPECT_EQ(1u, peer_.dynamic_entries_count()); + EXPECT_EQ(peer_.dynamic_entries().size(), peer_.dynamic_entries_count()); + EXPECT_EQ(static_count + 1, peer_.total_insertions()); + EXPECT_EQ(static_count + 1, peer_.index_size()); + + // Index() of entries reflects the insertion. + EXPECT_EQ(1u, table_.IndexOf(first_static_entry)); + // Static table has 61 entries. + EXPECT_EQ(62u, table_.IndexOf(entry)); + EXPECT_EQ(first_static_entry, table_.GetByIndex(1)); + EXPECT_EQ(entry, table_.GetByIndex(62)); + + // Evict |entry|. Table counts are again updated appropriately. + peer_.Evict(1); + EXPECT_EQ(0u, table_.size()); + EXPECT_EQ(0u, peer_.dynamic_entries_count()); + EXPECT_EQ(peer_.dynamic_entries().size(), peer_.dynamic_entries_count()); + EXPECT_EQ(static_count + 1, peer_.total_insertions()); + EXPECT_EQ(static_count, peer_.index_size()); + + // Index() of |first_static_entry| reflects the eviction. + EXPECT_EQ(1u, table_.IndexOf(first_static_entry)); + EXPECT_EQ(first_static_entry, table_.GetByIndex(1)); +} + +TEST_F(HpackHeaderTableTest, EntryIndexing) { + const HpackEntry* first_static_entry = table_.GetByIndex(1); + + // Static entries are queryable by name & value. + EXPECT_EQ(first_static_entry, table_.GetByName(first_static_entry->name())); + EXPECT_EQ(first_static_entry, + table_.GetByNameAndValue(first_static_entry->name(), + first_static_entry->value())); + + // Create a mix of entries which duplicate names, and names & values of both + // dynamic and static entries. + const HpackEntry* entry1 = table_.TryAddEntry(first_static_entry->name(), + first_static_entry->value()); + const HpackEntry* entry2 = + table_.TryAddEntry(first_static_entry->name(), "Value Four"); + const HpackEntry* entry3 = table_.TryAddEntry("key-1", "Value One"); + const HpackEntry* entry4 = table_.TryAddEntry("key-2", "Value Three"); + const HpackEntry* entry5 = table_.TryAddEntry("key-1", "Value Two"); + const HpackEntry* entry6 = table_.TryAddEntry("key-2", "Value Three"); + const HpackEntry* entry7 = table_.TryAddEntry("key-2", "Value Four"); + + // Entries are queryable under their current index. + EXPECT_EQ(entry7, table_.GetByIndex(62)); + EXPECT_EQ(entry6, table_.GetByIndex(63)); + EXPECT_EQ(entry5, table_.GetByIndex(64)); + EXPECT_EQ(entry4, table_.GetByIndex(65)); + EXPECT_EQ(entry3, table_.GetByIndex(66)); + EXPECT_EQ(entry2, table_.GetByIndex(67)); + EXPECT_EQ(entry1, table_.GetByIndex(68)); + EXPECT_EQ(first_static_entry, table_.GetByIndex(1)); + + // Querying by name returns the most recently added matching entry. + EXPECT_EQ(entry5, table_.GetByName("key-1")); + EXPECT_EQ(entry7, table_.GetByName("key-2")); + EXPECT_EQ(entry2->name(), + table_.GetByName(first_static_entry->name())->name()); + EXPECT_EQ(nullptr, table_.GetByName("not-present")); + + // Querying by name & value returns the lowest-index matching entry among + // static entries, and the highest-index one among dynamic entries. + EXPECT_EQ(entry3, table_.GetByNameAndValue("key-1", "Value One")); + EXPECT_EQ(entry5, table_.GetByNameAndValue("key-1", "Value Two")); + EXPECT_EQ(entry6, table_.GetByNameAndValue("key-2", "Value Three")); + EXPECT_EQ(entry7, table_.GetByNameAndValue("key-2", "Value Four")); + EXPECT_EQ(first_static_entry, + table_.GetByNameAndValue(first_static_entry->name(), + first_static_entry->value())); + EXPECT_EQ(entry2, + table_.GetByNameAndValue(first_static_entry->name(), "Value Four")); + EXPECT_EQ(nullptr, table_.GetByNameAndValue("key-1", "Not Present")); + EXPECT_EQ(nullptr, table_.GetByNameAndValue("not-present", "Value One")); + + // Evict |entry1|. Queries for its name & value now return the static entry. + // |entry2| remains queryable. + peer_.Evict(1); + EXPECT_EQ(first_static_entry, + table_.GetByNameAndValue(first_static_entry->name(), + first_static_entry->value())); + EXPECT_EQ(entry2, + table_.GetByNameAndValue(first_static_entry->name(), "Value Four")); + + // Evict |entry2|. Queries by its name & value are not found. + peer_.Evict(1); + EXPECT_EQ(nullptr, + table_.GetByNameAndValue(first_static_entry->name(), "Value Four")); +} + +TEST_F(HpackHeaderTableTest, SetSizes) { + SpdyString key = "key", value = "value"; + const HpackEntry* entry1 = table_.TryAddEntry(key, value); + const HpackEntry* entry2 = table_.TryAddEntry(key, value); + const HpackEntry* entry3 = table_.TryAddEntry(key, value); + + // Set exactly large enough. No Evictions. + size_t max_size = entry1->Size() + entry2->Size() + entry3->Size(); + table_.SetMaxSize(max_size); + EXPECT_EQ(3u, peer_.dynamic_entries().size()); + + // Set just too small. One eviction. + max_size = entry1->Size() + entry2->Size() + entry3->Size() - 1; + table_.SetMaxSize(max_size); + EXPECT_EQ(2u, peer_.dynamic_entries().size()); + + // Changing SETTINGS_HEADER_TABLE_SIZE. + EXPECT_EQ(kDefaultHeaderTableSizeSetting, table_.settings_size_bound()); + // In production, the size passed to SetSettingsHeaderTableSize is never + // larger than table_.settings_size_bound(). + table_.SetSettingsHeaderTableSize(kDefaultHeaderTableSizeSetting * 3 + 1); + EXPECT_EQ(kDefaultHeaderTableSizeSetting * 3 + 1, table_.max_size()); + + // SETTINGS_HEADER_TABLE_SIZE upper-bounds |table_.max_size()|, + // and will force evictions. + max_size = entry3->Size() - 1; + table_.SetSettingsHeaderTableSize(max_size); + EXPECT_EQ(max_size, table_.max_size()); + EXPECT_EQ(max_size, table_.settings_size_bound()); + EXPECT_EQ(0u, peer_.dynamic_entries().size()); +} + +TEST_F(HpackHeaderTableTest, EvictionCountForEntry) { + SpdyString key = "key", value = "value"; + const HpackEntry* entry1 = table_.TryAddEntry(key, value); + const HpackEntry* entry2 = table_.TryAddEntry(key, value); + size_t entry3_size = HpackEntry::Size(key, value); + + // Just enough capacity for third entry. + table_.SetMaxSize(entry1->Size() + entry2->Size() + entry3_size); + EXPECT_EQ(0u, peer_.EvictionCountForEntry(key, value)); + EXPECT_EQ(1u, peer_.EvictionCountForEntry(key, value + "x")); + + // No extra capacity. Third entry would force evictions. + table_.SetMaxSize(entry1->Size() + entry2->Size()); + EXPECT_EQ(1u, peer_.EvictionCountForEntry(key, value)); + EXPECT_EQ(2u, peer_.EvictionCountForEntry(key, value + "x")); +} + +TEST_F(HpackHeaderTableTest, EvictionCountToReclaim) { + SpdyString key = "key", value = "value"; + const HpackEntry* entry1 = table_.TryAddEntry(key, value); + const HpackEntry* entry2 = table_.TryAddEntry(key, value); + + EXPECT_EQ(1u, peer_.EvictionCountToReclaim(1)); + EXPECT_EQ(1u, peer_.EvictionCountToReclaim(entry1->Size())); + EXPECT_EQ(2u, peer_.EvictionCountToReclaim(entry1->Size() + 1)); + EXPECT_EQ(2u, peer_.EvictionCountToReclaim(entry1->Size() + entry2->Size())); +} + +// Fill a header table with entries. Make sure the entries are in +// reverse order in the header table. +TEST_F(HpackHeaderTableTest, TryAddEntryBasic) { + EXPECT_EQ(0u, table_.size()); + EXPECT_EQ(table_.settings_size_bound(), table_.max_size()); + + HpackEntryVector entries = MakeEntriesOfTotalSize(table_.max_size()); + + // Most of the checks are in AddEntriesExpectNoEviction(). + AddEntriesExpectNoEviction(entries); + EXPECT_EQ(table_.max_size(), table_.size()); + EXPECT_EQ(table_.settings_size_bound(), table_.size()); +} + +// Fill a header table with entries, and then ramp the table's max +// size down to evict an entry one at a time. Make sure the eviction +// happens as expected. +TEST_F(HpackHeaderTableTest, SetMaxSize) { + HpackEntryVector entries = + MakeEntriesOfTotalSize(kDefaultHeaderTableSizeSetting / 2); + AddEntriesExpectNoEviction(entries); + + for (auto it = entries.begin(); it != entries.end(); ++it) { + size_t expected_count = distance(it, entries.end()); + EXPECT_EQ(expected_count, peer_.dynamic_entries().size()); + + table_.SetMaxSize(table_.size() + 1); + EXPECT_EQ(expected_count, peer_.dynamic_entries().size()); + + table_.SetMaxSize(table_.size()); + EXPECT_EQ(expected_count, peer_.dynamic_entries().size()); + + --expected_count; + table_.SetMaxSize(table_.size() - 1); + EXPECT_EQ(expected_count, peer_.dynamic_entries().size()); + } + EXPECT_EQ(0u, table_.size()); +} + +// Fill a header table with entries, and then add an entry just big +// enough to cause eviction of all but one entry. Make sure the +// eviction happens as expected and the long entry is inserted into +// the table. +TEST_F(HpackHeaderTableTest, TryAddEntryEviction) { + HpackEntryVector entries = MakeEntriesOfTotalSize(table_.max_size()); + AddEntriesExpectNoEviction(entries); + + const HpackEntry* survivor_entry = table_.GetByIndex(61 + 1); + HpackEntry long_entry = + MakeEntryOfSize(table_.max_size() - survivor_entry->Size()); + + // All dynamic entries but the first are to be evicted. + EXPECT_EQ(peer_.dynamic_entries().size() - 1, + peer_.EvictionSet(long_entry.name(), long_entry.value()).size()); + + const HpackEntry* new_entry = + table_.TryAddEntry(long_entry.name(), long_entry.value()); + EXPECT_EQ(62u, table_.IndexOf(new_entry)); + EXPECT_EQ(2u, peer_.dynamic_entries().size()); + EXPECT_EQ(table_.GetByIndex(63), survivor_entry); + EXPECT_EQ(table_.GetByIndex(62), new_entry); +} + +// Fill a header table with entries, and then add an entry bigger than +// the entire table. Make sure no entry remains in the table. +TEST_F(HpackHeaderTableTest, TryAddTooLargeEntry) { + HpackEntryVector entries = MakeEntriesOfTotalSize(table_.max_size()); + AddEntriesExpectNoEviction(entries); + + const HpackEntry long_entry = MakeEntryOfSize(table_.max_size() + 1); + + // All entries are to be evicted. + EXPECT_EQ(peer_.dynamic_entries().size(), + peer_.EvictionSet(long_entry.name(), long_entry.value()).size()); + + const HpackEntry* new_entry = + table_.TryAddEntry(long_entry.name(), long_entry.value()); + EXPECT_EQ(new_entry, static_cast<HpackEntry*>(nullptr)); + EXPECT_EQ(0u, peer_.dynamic_entries().size()); +} + +TEST_F(HpackHeaderTableTest, EntryNamesDiffer) { + HpackEntry entry1("header", "value"); + HpackEntry entry2("HEADER", "value"); + + HpackHeaderTable::EntryHasher hasher; + EXPECT_NE(hasher(&entry1), hasher(&entry2)); + + HpackHeaderTable::EntriesEq eq; + EXPECT_FALSE(eq(&entry1, &entry2)); +} + +TEST_F(HpackHeaderTableTest, EntryValuesDiffer) { + HpackEntry entry1("header", "value"); + HpackEntry entry2("header", "VALUE"); + + HpackHeaderTable::EntryHasher hasher; + EXPECT_NE(hasher(&entry1), hasher(&entry2)); + + HpackHeaderTable::EntriesEq eq; + EXPECT_FALSE(eq(&entry1, &entry2)); +} + +TEST_F(HpackHeaderTableTest, EntriesEqual) { + HpackEntry entry1(DynamicEntry("name", "value")); + HpackEntry entry2(DynamicEntry("name", "value")); + + HpackHeaderTable::EntryHasher hasher; + EXPECT_EQ(hasher(&entry1), hasher(&entry2)); + + HpackHeaderTable::EntriesEq eq; + EXPECT_TRUE(eq(&entry1, &entry2)); +} + +TEST_F(HpackHeaderTableTest, StaticAndDynamicEntriesEqual) { + HpackEntry entry1("name", "value"); + HpackEntry entry2(DynamicEntry("name", "value")); + + HpackHeaderTable::EntryHasher hasher; + EXPECT_EQ(hasher(&entry1), hasher(&entry2)); + + HpackHeaderTable::EntriesEq eq; + EXPECT_TRUE(eq(&entry1, &entry2)); +} + +} // namespace + +} // namespace spdy
diff --git a/spdy/core/hpack/hpack_huffman_table.cc b/spdy/core/hpack/hpack_huffman_table.cc new file mode 100644 index 0000000..c917767 --- /dev/null +++ b/spdy/core/hpack/hpack_huffman_table.cc
@@ -0,0 +1,151 @@ +// Copyright 2014 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_huffman_table.h" + +#include <algorithm> +#include <cmath> +#include <limits> +#include <memory> + +#include "base/logging.h" +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_output_stream.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_estimate_memory_usage.h" + +namespace spdy { + +namespace { + +bool SymbolLengthAndIdCompare(const HpackHuffmanSymbol& a, + const HpackHuffmanSymbol& b) { + if (a.length == b.length) { + return a.id < b.id; + } + return a.length < b.length; +} +bool SymbolIdCompare(const HpackHuffmanSymbol& a, const HpackHuffmanSymbol& b) { + return a.id < b.id; +} + +} // namespace + +HpackHuffmanTable::HpackHuffmanTable() : pad_bits_(0), failed_symbol_id_(0) {} + +HpackHuffmanTable::~HpackHuffmanTable() = default; + +bool HpackHuffmanTable::Initialize(const HpackHuffmanSymbol* input_symbols, + size_t symbol_count) { + CHECK(!IsInitialized()); + DCHECK_LE(symbol_count, std::numeric_limits<uint16_t>::max()); + + std::vector<Symbol> symbols(symbol_count); + // Validate symbol id sequence, and copy into |symbols|. + for (uint16_t i = 0; i < symbol_count; i++) { + if (i != input_symbols[i].id) { + failed_symbol_id_ = i; + return false; + } + symbols[i] = input_symbols[i]; + } + // Order on length and ID ascending, to verify symbol codes are canonical. + std::sort(symbols.begin(), symbols.end(), SymbolLengthAndIdCompare); + if (symbols[0].code != 0) { + failed_symbol_id_ = 0; + return false; + } + for (size_t i = 1; i != symbols.size(); i++) { + unsigned code_shift = 32 - symbols[i - 1].length; + uint32_t code = symbols[i - 1].code + (1 << code_shift); + + if (code != symbols[i].code) { + failed_symbol_id_ = symbols[i].id; + return false; + } + if (code < symbols[i - 1].code) { + // An integer overflow occurred. This implies the input + // lengths do not represent a valid Huffman code. + failed_symbol_id_ = symbols[i].id; + return false; + } + } + if (symbols.back().length < 8) { + // At least one code (such as an EOS symbol) must be 8 bits or longer. + // Without this, some inputs will not be encodable in a whole number + // of bytes. + return false; + } + pad_bits_ = static_cast<uint8_t>(symbols.back().code >> 24); + + // Order on symbol ID ascending. + std::sort(symbols.begin(), symbols.end(), SymbolIdCompare); + BuildEncodeTable(symbols); + return true; +} + +void HpackHuffmanTable::BuildEncodeTable(const std::vector<Symbol>& symbols) { + for (size_t i = 0; i != symbols.size(); i++) { + const Symbol& symbol = symbols[i]; + CHECK_EQ(i, symbol.id); + code_by_id_.push_back(symbol.code); + length_by_id_.push_back(symbol.length); + } +} + +bool HpackHuffmanTable::IsInitialized() const { + return !code_by_id_.empty(); +} + +void HpackHuffmanTable::EncodeString(SpdyStringPiece in, + HpackOutputStream* out) const { + size_t bit_remnant = 0; + for (size_t i = 0; i != in.size(); i++) { + uint16_t symbol_id = static_cast<uint8_t>(in[i]); + CHECK_GT(code_by_id_.size(), symbol_id); + + // Load, and shift code to low bits. + unsigned length = length_by_id_[symbol_id]; + uint32_t code = code_by_id_[symbol_id] >> (32 - length); + + bit_remnant = (bit_remnant + length) % 8; + + if (length > 24) { + out->AppendBits(static_cast<uint8_t>(code >> 24), length - 24); + length = 24; + } + if (length > 16) { + out->AppendBits(static_cast<uint8_t>(code >> 16), length - 16); + length = 16; + } + if (length > 8) { + out->AppendBits(static_cast<uint8_t>(code >> 8), length - 8); + length = 8; + } + out->AppendBits(static_cast<uint8_t>(code), length); + } + if (bit_remnant != 0) { + // Pad current byte as required. + out->AppendBits(pad_bits_ >> bit_remnant, 8 - bit_remnant); + } +} + +size_t HpackHuffmanTable::EncodedSize(SpdyStringPiece in) const { + size_t bit_count = 0; + for (size_t i = 0; i != in.size(); i++) { + uint16_t symbol_id = static_cast<uint8_t>(in[i]); + CHECK_GT(code_by_id_.size(), symbol_id); + + bit_count += length_by_id_[symbol_id]; + } + if (bit_count % 8 != 0) { + bit_count += 8 - bit_count % 8; + } + return bit_count / 8; +} + +size_t HpackHuffmanTable::EstimateMemoryUsage() const { + return SpdyEstimateMemoryUsage(code_by_id_) + + SpdyEstimateMemoryUsage(length_by_id_); +} + +} // namespace spdy
diff --git a/spdy/core/hpack/hpack_huffman_table.h b/spdy/core/hpack/hpack_huffman_table.h new file mode 100644 index 0000000..80d9e52 --- /dev/null +++ b/spdy/core/hpack/hpack_huffman_table.h
@@ -0,0 +1,76 @@ +// Copyright 2014 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#ifndef QUICHE_SPDY_CORE_HPACK_HPACK_HUFFMAN_TABLE_H_ +#define QUICHE_SPDY_CORE_HPACK_HPACK_HUFFMAN_TABLE_H_ + +#include <cstddef> +#include <cstdint> +#include <vector> + +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_constants.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_export.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_string.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_string_piece.h" + +namespace spdy { + +namespace test { +class HpackHuffmanTablePeer; +} // namespace test + +class HpackOutputStream; + +// HpackHuffmanTable encodes string literals using a constructed canonical +// Huffman code. Once initialized, an instance is read only and may be accessed +// only through its const interface. +class SPDY_EXPORT_PRIVATE HpackHuffmanTable { + public: + friend class test::HpackHuffmanTablePeer; + + typedef HpackHuffmanSymbol Symbol; + + HpackHuffmanTable(); + ~HpackHuffmanTable(); + + // Prepares HpackHuffmanTable to encode the canonical Huffman code as + // determined by the given symbols. Must be called exactly once. + // Returns false if the input symbols define an invalid coding, and true + // otherwise. Symbols must be presented in ascending ID order with no gaps, + // and |symbol_count| must fit in a uint16_t. + bool Initialize(const Symbol* input_symbols, size_t symbol_count); + + // Returns whether Initialize() has been successfully called. + bool IsInitialized() const; + + // Encodes the input string to the output stream using the table's Huffman + // context. + void EncodeString(SpdyStringPiece in, HpackOutputStream* out) const; + + // Returns the encoded size of the input string. + size_t EncodedSize(SpdyStringPiece in) const; + + // Returns the estimate of dynamically allocated memory in bytes. + size_t EstimateMemoryUsage() const; + + private: + // Expects symbols ordered on ID ascending. + void BuildEncodeTable(const std::vector<Symbol>& symbols); + + // Symbol code and code length, in ascending symbol ID order. + // Codes are stored in the most-significant bits of the word. + std::vector<uint32_t> code_by_id_; + std::vector<uint8_t> length_by_id_; + + // The first 8 bits of the longest code. Applied when generating padding bits. + uint8_t pad_bits_; + + // If initialization fails, preserve the symbol ID which failed validation + // for examination in tests. + uint16_t failed_symbol_id_; +}; + +} // namespace spdy + +#endif // QUICHE_SPDY_CORE_HPACK_HPACK_HUFFMAN_TABLE_H_
diff --git a/spdy/core/hpack/hpack_huffman_table_test.cc b/spdy/core/hpack/hpack_huffman_table_test.cc new file mode 100644 index 0000000..f30926c --- /dev/null +++ b/spdy/core/hpack/hpack_huffman_table_test.cc
@@ -0,0 +1,309 @@ +// Copyright 2014 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_huffman_table.h" + +#include <utility> + +#include "base/macros.h" +#include "testing/gmock/include/gmock/gmock.h" +#include "testing/gtest/include/gtest/gtest.h" +#include "net/third_party/quiche/src/http2/hpack/huffman/hpack_huffman_decoder.h" +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_constants.h" +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_output_stream.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_arraysize.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_string_utils.h" + +namespace spdy { + +namespace test { + +class HpackHuffmanTablePeer { + public: + explicit HpackHuffmanTablePeer(const HpackHuffmanTable& table) + : table_(table) {} + + const std::vector<uint32_t>& code_by_id() const { return table_.code_by_id_; } + const std::vector<uint8_t>& length_by_id() const { + return table_.length_by_id_; + } + uint8_t pad_bits() const { return table_.pad_bits_; } + uint16_t failed_symbol_id() const { return table_.failed_symbol_id_; } + + private: + const HpackHuffmanTable& table_; +}; + +namespace { + +// Tests of the ability to encode some canonical Huffman code, +// not just the one defined in the RFC 7541. +class GenericHuffmanTableTest : public ::testing::Test { + protected: + GenericHuffmanTableTest() : table_(), peer_(table_) {} + + SpdyString EncodeString(SpdyStringPiece input) { + SpdyString result; + HpackOutputStream output_stream; + table_.EncodeString(input, &output_stream); + + output_stream.TakeString(&result); + // Verify EncodedSize() agrees with EncodeString(). + EXPECT_EQ(result.size(), table_.EncodedSize(input)); + return result; + } + + HpackHuffmanTable table_; + HpackHuffmanTablePeer peer_; +}; + +TEST_F(GenericHuffmanTableTest, InitializeEdgeCases) { + { + // Verify eight symbols can be encoded with 3 bits per symbol. + HpackHuffmanSymbol code[] = {{0b00000000000000000000000000000000, 3, 0}, + {0b00100000000000000000000000000000, 3, 1}, + {0b01000000000000000000000000000000, 3, 2}, + {0b01100000000000000000000000000000, 3, 3}, + {0b10000000000000000000000000000000, 3, 4}, + {0b10100000000000000000000000000000, 3, 5}, + {0b11000000000000000000000000000000, 3, 6}, + {0b11100000000000000000000000000000, 8, 7}}; + HpackHuffmanTable table; + EXPECT_TRUE(table.Initialize(code, SPDY_ARRAYSIZE(code))); + } + { + // But using 2 bits with one symbol overflows the code. + HpackHuffmanSymbol code[] = { + {0b01000000000000000000000000000000, 3, 0}, + {0b01100000000000000000000000000000, 3, 1}, + {0b00000000000000000000000000000000, 2, 2}, + {0b10000000000000000000000000000000, 3, 3}, + {0b10100000000000000000000000000000, 3, 4}, + {0b11000000000000000000000000000000, 3, 5}, + {0b11100000000000000000000000000000, 3, 6}, + {0b00000000000000000000000000000000, 8, 7}}; // Overflow. + HpackHuffmanTable table; + EXPECT_FALSE(table.Initialize(code, SPDY_ARRAYSIZE(code))); + EXPECT_EQ(7, HpackHuffmanTablePeer(table).failed_symbol_id()); + } + { + // Verify four symbols can be encoded with incremental bits per symbol. + HpackHuffmanSymbol code[] = {{0b00000000000000000000000000000000, 1, 0}, + {0b10000000000000000000000000000000, 2, 1}, + {0b11000000000000000000000000000000, 3, 2}, + {0b11100000000000000000000000000000, 8, 3}}; + HpackHuffmanTable table; + EXPECT_TRUE(table.Initialize(code, SPDY_ARRAYSIZE(code))); + } + { + // But repeating a length overflows the code. + HpackHuffmanSymbol code[] = { + {0b00000000000000000000000000000000, 1, 0}, + {0b10000000000000000000000000000000, 2, 1}, + {0b11000000000000000000000000000000, 2, 2}, + {0b00000000000000000000000000000000, 8, 3}}; // Overflow. + HpackHuffmanTable table; + EXPECT_FALSE(table.Initialize(code, SPDY_ARRAYSIZE(code))); + EXPECT_EQ(3, HpackHuffmanTablePeer(table).failed_symbol_id()); + } + { + // Symbol IDs must be assigned sequentially with no gaps. + HpackHuffmanSymbol code[] = { + {0b00000000000000000000000000000000, 1, 0}, + {0b10000000000000000000000000000000, 2, 1}, + {0b11000000000000000000000000000000, 3, 1}, // Repeat. + {0b11100000000000000000000000000000, 8, 3}}; + HpackHuffmanTable table; + EXPECT_FALSE(table.Initialize(code, SPDY_ARRAYSIZE(code))); + EXPECT_EQ(2, HpackHuffmanTablePeer(table).failed_symbol_id()); + } + { + // Canonical codes must begin with zero. + HpackHuffmanSymbol code[] = {{0b10000000000000000000000000000000, 4, 0}, + {0b10010000000000000000000000000000, 4, 1}, + {0b10100000000000000000000000000000, 4, 2}, + {0b10110000000000000000000000000000, 8, 3}}; + HpackHuffmanTable table; + EXPECT_FALSE(table.Initialize(code, SPDY_ARRAYSIZE(code))); + EXPECT_EQ(0, HpackHuffmanTablePeer(table).failed_symbol_id()); + } + { + // Codes must match the expected canonical sequence. + HpackHuffmanSymbol code[] = { + {0b00000000000000000000000000000000, 2, 0}, + {0b01000000000000000000000000000000, 2, 1}, + {0b11000000000000000000000000000000, 2, 2}, // Code not canonical. + {0b10000000000000000000000000000000, 8, 3}}; + HpackHuffmanTable table; + EXPECT_FALSE(table.Initialize(code, SPDY_ARRAYSIZE(code))); + EXPECT_EQ(2, HpackHuffmanTablePeer(table).failed_symbol_id()); + } + { + // At least one code must have a length of 8 bits (to ensure pad-ability). + HpackHuffmanSymbol code[] = {{0b00000000000000000000000000000000, 1, 0}, + {0b10000000000000000000000000000000, 2, 1}, + {0b11000000000000000000000000000000, 3, 2}, + {0b11100000000000000000000000000000, 7, 3}}; + HpackHuffmanTable table; + EXPECT_FALSE(table.Initialize(code, SPDY_ARRAYSIZE(code))); + } +} + +TEST_F(GenericHuffmanTableTest, ValidateInternalsWithSmallCode) { + HpackHuffmanSymbol code[] = { + {0b01100000000000000000000000000000, 4, 0}, // 3rd. + {0b01110000000000000000000000000000, 4, 1}, // 4th. + {0b00000000000000000000000000000000, 2, 2}, // 1st assigned code. + {0b01000000000000000000000000000000, 3, 3}, // 2nd. + {0b10000000000000000000000000000000, 5, 4}, // 5th. + {0b10001000000000000000000000000000, 5, 5}, // 6th. + {0b10011000000000000000000000000000, 8, 6}, // 8th. + {0b10010000000000000000000000000000, 5, 7}}; // 7th. + EXPECT_TRUE(table_.Initialize(code, SPDY_ARRAYSIZE(code))); + + ASSERT_EQ(SPDY_ARRAYSIZE(code), peer_.code_by_id().size()); + ASSERT_EQ(SPDY_ARRAYSIZE(code), peer_.length_by_id().size()); + for (size_t i = 0; i < SPDY_ARRAYSIZE(code); ++i) { + EXPECT_EQ(code[i].code, peer_.code_by_id()[i]); + EXPECT_EQ(code[i].length, peer_.length_by_id()[i]); + } + + EXPECT_EQ(0b10011000, peer_.pad_bits()); + + char input_storage[] = {2, 3, 2, 7, 4}; + SpdyStringPiece input(input_storage, SPDY_ARRAYSIZE(input_storage)); + // By symbol: (2) 00 (3) 010 (2) 00 (7) 10010 (4) 10000 (6 as pad) 1001100. + char expect_storage[] = {0b00010001, 0b00101000, 0b01001100}; + SpdyStringPiece expect(expect_storage, SPDY_ARRAYSIZE(expect_storage)); + EXPECT_EQ(expect, EncodeString(input)); +} + +// Tests of the ability to encode the HPACK Huffman Code, defined in: +// https://httpwg.github.io/specs/rfc7541.html#huffman.code +class HpackHuffmanTableTest : public GenericHuffmanTableTest { + protected: + void SetUp() override { + EXPECT_TRUE(table_.Initialize(HpackHuffmanCodeVector().data(), + HpackHuffmanCodeVector().size())); + EXPECT_TRUE(table_.IsInitialized()); + } + + // Use http2::HpackHuffmanDecoder for roundtrip tests. + void DecodeString(const SpdyString& encoded, SpdyString* out) { + http2::HpackHuffmanDecoder decoder; + out->clear(); + EXPECT_TRUE(decoder.Decode(encoded, out)); + } +}; + +TEST_F(HpackHuffmanTableTest, InitializeHpackCode) { + EXPECT_EQ(peer_.pad_bits(), 0b11111111); // First 8 bits of EOS. +} + +TEST_F(HpackHuffmanTableTest, SpecRequestExamples) { + SpdyString buffer; + SpdyString test_table[] = { + SpdyHexDecode("f1e3c2e5f23a6ba0ab90f4ff"), + "www.example.com", + SpdyHexDecode("a8eb10649cbf"), + "no-cache", + SpdyHexDecode("25a849e95ba97d7f"), + "custom-key", + SpdyHexDecode("25a849e95bb8e8b4bf"), + "custom-value", + }; + // Round-trip each test example. + for (size_t i = 0; i != SPDY_ARRAYSIZE(test_table); i += 2) { + const SpdyString& encodedFixture(test_table[i]); + const SpdyString& decodedFixture(test_table[i + 1]); + DecodeString(encodedFixture, &buffer); + EXPECT_EQ(decodedFixture, buffer); + buffer = EncodeString(decodedFixture); + EXPECT_EQ(encodedFixture, buffer); + } +} + +TEST_F(HpackHuffmanTableTest, SpecResponseExamples) { + SpdyString buffer; + SpdyString test_table[] = { + SpdyHexDecode("6402"), + "302", + SpdyHexDecode("aec3771a4b"), + "private", + SpdyHexDecode("d07abe941054d444a8200595040b8166" + "e082a62d1bff"), + "Mon, 21 Oct 2013 20:13:21 GMT", + SpdyHexDecode("9d29ad171863c78f0b97c8e9ae82ae43" + "d3"), + "https://www.example.com", + SpdyHexDecode("94e7821dd7f2e6c7b335dfdfcd5b3960" + "d5af27087f3672c1ab270fb5291f9587" + "316065c003ed4ee5b1063d5007"), + "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1", + }; + // Round-trip each test example. + for (size_t i = 0; i != SPDY_ARRAYSIZE(test_table); i += 2) { + const SpdyString& encodedFixture(test_table[i]); + const SpdyString& decodedFixture(test_table[i + 1]); + DecodeString(encodedFixture, &buffer); + EXPECT_EQ(decodedFixture, buffer); + buffer = EncodeString(decodedFixture); + EXPECT_EQ(encodedFixture, buffer); + } +} + +TEST_F(HpackHuffmanTableTest, RoundTripIndividualSymbols) { + for (size_t i = 0; i != 256; i++) { + char c = static_cast<char>(i); + char storage[3] = {c, c, c}; + SpdyStringPiece input(storage, SPDY_ARRAYSIZE(storage)); + SpdyString buffer_in = EncodeString(input); + SpdyString buffer_out; + DecodeString(buffer_in, &buffer_out); + EXPECT_EQ(input, buffer_out); + } +} + +TEST_F(HpackHuffmanTableTest, RoundTripSymbolSequence) { + char storage[512]; + for (size_t i = 0; i != 256; i++) { + storage[i] = static_cast<char>(i); + storage[511 - i] = static_cast<char>(i); + } + SpdyStringPiece input(storage, SPDY_ARRAYSIZE(storage)); + SpdyString buffer_in = EncodeString(input); + SpdyString buffer_out; + DecodeString(buffer_in, &buffer_out); + EXPECT_EQ(input, buffer_out); +} + +TEST_F(HpackHuffmanTableTest, EncodedSizeAgreesWithEncodeString) { + SpdyString test_table[] = { + "", + "Mon, 21 Oct 2013 20:13:21 GMT", + "https://www.example.com", + "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1", + SpdyString(1, '\0'), + SpdyString("foo\0bar", 7), + SpdyString(256, '\0'), + }; + for (size_t i = 0; i != 256; ++i) { + // Expand last |test_table| entry to cover all codes. + test_table[SPDY_ARRAYSIZE(test_table) - 1][i] = static_cast<char>(i); + } + + HpackOutputStream output_stream; + SpdyString encoding; + for (size_t i = 0; i != SPDY_ARRAYSIZE(test_table); ++i) { + table_.EncodeString(test_table[i], &output_stream); + output_stream.TakeString(&encoding); + EXPECT_EQ(encoding.size(), table_.EncodedSize(test_table[i])); + } +} + +} // namespace + +} // namespace test + +} // namespace spdy
diff --git a/spdy/core/hpack/hpack_output_stream.cc b/spdy/core/hpack/hpack_output_stream.cc new file mode 100644 index 0000000..30b5662 --- /dev/null +++ b/spdy/core/hpack/hpack_output_stream.cc
@@ -0,0 +1,97 @@ +// Copyright 2014 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_output_stream.h" + +#include <utility> + +#include "base/logging.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_estimate_memory_usage.h" + +namespace spdy { + +HpackOutputStream::HpackOutputStream() : bit_offset_(0) {} + +HpackOutputStream::~HpackOutputStream() = default; + +void HpackOutputStream::AppendBits(uint8_t bits, size_t bit_size) { + DCHECK_GT(bit_size, 0u); + DCHECK_LE(bit_size, 8u); + DCHECK_EQ(bits >> bit_size, 0); + size_t new_bit_offset = bit_offset_ + bit_size; + if (bit_offset_ == 0) { + // Buffer ends on a byte boundary. + DCHECK_LE(bit_size, 8u); + buffer_.append(1, bits << (8 - bit_size)); + } else if (new_bit_offset <= 8) { + // Buffer does not end on a byte boundary but the given bits fit + // in the remainder of the last byte. + buffer_.back() |= bits << (8 - new_bit_offset); + } else { + // Buffer does not end on a byte boundary and the given bits do + // not fit in the remainder of the last byte. + buffer_.back() |= bits >> (new_bit_offset - 8); + buffer_.append(1, bits << (16 - new_bit_offset)); + } + bit_offset_ = new_bit_offset % 8; +} + +void HpackOutputStream::AppendPrefix(HpackPrefix prefix) { + AppendBits(prefix.bits, prefix.bit_size); +} + +void HpackOutputStream::AppendBytes(SpdyStringPiece buffer) { + DCHECK_EQ(bit_offset_, 0u); + buffer_.append(buffer.data(), buffer.size()); +} + +void HpackOutputStream::AppendUint32(uint32_t I) { + // The algorithm below is adapted from the pseudocode in 6.1. + size_t N = 8 - bit_offset_; + uint8_t max_first_byte = static_cast<uint8_t>((1 << N) - 1); + if (I < max_first_byte) { + AppendBits(static_cast<uint8_t>(I), N); + } else { + AppendBits(max_first_byte, N); + I -= max_first_byte; + while ((I & ~0x7f) != 0) { + buffer_.append(1, (I & 0x7f) | 0x80); + I >>= 7; + } + AppendBits(static_cast<uint8_t>(I), 8); + } +} + +void HpackOutputStream::TakeString(SpdyString* output) { + // This must hold, since all public functions cause the buffer to + // end on a byte boundary. + DCHECK_EQ(bit_offset_, 0u); + buffer_.swap(*output); + buffer_.clear(); + bit_offset_ = 0; +} + +void HpackOutputStream::BoundedTakeString(size_t max_size, SpdyString* output) { + if (buffer_.size() > max_size) { + // Save off overflow bytes to temporary string (causes a copy). + SpdyString overflow(buffer_.data() + max_size, buffer_.size() - max_size); + + // Resize buffer down to the given limit. + buffer_.resize(max_size); + + // Give buffer to output string. + *output = std::move(buffer_); + + // Reset to contain overflow. + buffer_ = std::move(overflow); + } else { + TakeString(output); + } +} + +size_t HpackOutputStream::EstimateMemoryUsage() const { + return SpdyEstimateMemoryUsage(buffer_); +} + +} // namespace spdy
diff --git a/spdy/core/hpack/hpack_output_stream.h b/spdy/core/hpack/hpack_output_stream.h new file mode 100644 index 0000000..450803f --- /dev/null +++ b/spdy/core/hpack/hpack_output_stream.h
@@ -0,0 +1,76 @@ +// Copyright 2014 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#ifndef QUICHE_SPDY_CORE_HPACK_HPACK_OUTPUT_STREAM_H_ +#define QUICHE_SPDY_CORE_HPACK_HPACK_OUTPUT_STREAM_H_ + +#include <cstdint> +#include <map> + +#include "base/macros.h" +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_constants.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_export.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_string.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_string_piece.h" + +// All section references below are to +// http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-08 + +namespace spdy { + +// An HpackOutputStream handles all the low-level details of encoding +// header fields. +class SPDY_EXPORT_PRIVATE HpackOutputStream { + public: + HpackOutputStream(); + HpackOutputStream(const HpackOutputStream&) = delete; + HpackOutputStream& operator=(const HpackOutputStream&) = delete; + ~HpackOutputStream(); + + // Appends the lower |bit_size| bits of |bits| to the internal buffer. + // + // |bit_size| must be > 0 and <= 8. |bits| must not have any bits + // set other than the lower |bit_size| bits. + void AppendBits(uint8_t bits, size_t bit_size); + + // Simply forwards to AppendBits(prefix.bits, prefix.bit-size). + void AppendPrefix(HpackPrefix prefix); + + // Directly appends |buffer|. + void AppendBytes(SpdyStringPiece buffer); + + // Appends the given integer using the representation described in + // 6.1. If the internal buffer ends on a byte boundary, the prefix + // length N is taken to be 8; otherwise, it is taken to be the + // number of bits to the next byte boundary. + // + // It is guaranteed that the internal buffer will end on a byte + // boundary after this function is called. + void AppendUint32(uint32_t I); + + // Swaps the internal buffer with |output|, then resets state. + void TakeString(SpdyString* output); + + // Gives up to |max_size| bytes of the internal buffer to |output|. Resets + // internal state with the overflow. + void BoundedTakeString(size_t max_size, SpdyString* output); + + // Size in bytes of stream's internal buffer. + size_t size() const { return buffer_.size(); } + + // Returns the estimate of dynamically allocated memory in bytes. + size_t EstimateMemoryUsage() const; + + private: + // The internal bit buffer. + SpdyString buffer_; + + // If 0, the buffer ends on a byte boundary. If non-zero, the buffer + // ends on the nth most significant bit. Guaranteed to be < 8. + size_t bit_offset_; +}; + +} // namespace spdy + +#endif // QUICHE_SPDY_CORE_HPACK_HPACK_OUTPUT_STREAM_H_
diff --git a/spdy/core/hpack/hpack_output_stream_test.cc b/spdy/core/hpack/hpack_output_stream_test.cc new file mode 100644 index 0000000..823c41b --- /dev/null +++ b/spdy/core/hpack/hpack_output_stream_test.cc
@@ -0,0 +1,276 @@ +// Copyright 2014 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_output_stream.h" + +#include <cstddef> + +#include "testing/gtest/include/gtest/gtest.h" + +namespace spdy { + +namespace { + +// Make sure that AppendBits() appends bits starting from the most +// significant bit, and that it can handle crossing a byte boundary. +TEST(HpackOutputStreamTest, AppendBits) { + HpackOutputStream output_stream; + SpdyString expected_str; + + output_stream.AppendBits(0x1, 1); + expected_str.append(1, 0x00); + expected_str.back() |= (0x1 << 7); + + output_stream.AppendBits(0x0, 1); + + output_stream.AppendBits(0x3, 2); + *expected_str.rbegin() |= (0x3 << 4); + + output_stream.AppendBits(0x0, 2); + + // Byte-crossing append. + output_stream.AppendBits(0x7, 3); + *expected_str.rbegin() |= (0x7 >> 1); + expected_str.append(1, 0x00); + expected_str.back() |= (0x7 << 7); + + output_stream.AppendBits(0x0, 7); + + SpdyString str; + output_stream.TakeString(&str); + EXPECT_EQ(expected_str, str); +} + +// Utility function to return I as a string encoded with an N-bit +// prefix. +SpdyString EncodeUint32(uint8_t N, uint32_t I) { + HpackOutputStream output_stream; + if (N < 8) { + output_stream.AppendBits(0x00, 8 - N); + } + output_stream.AppendUint32(I); + SpdyString str; + output_stream.TakeString(&str); + return str; +} + +// The {Number}ByteIntegersEightBitPrefix tests below test that +// certain integers are encoded correctly with an 8-bit prefix in +// exactly {Number} bytes. + +TEST(HpackOutputStreamTest, OneByteIntegersEightBitPrefix) { + // Minimum. + EXPECT_EQ(SpdyString("\x00", 1), EncodeUint32(8, 0x00)); + EXPECT_EQ("\x7f", EncodeUint32(8, 0x7f)); + // Maximum. + EXPECT_EQ("\xfe", EncodeUint32(8, 0xfe)); +} + +TEST(HpackOutputStreamTest, TwoByteIntegersEightBitPrefix) { + // Minimum. + EXPECT_EQ(SpdyString("\xff\x00", 2), EncodeUint32(8, 0xff)); + EXPECT_EQ("\xff\x01", EncodeUint32(8, 0x0100)); + // Maximum. + EXPECT_EQ("\xff\x7f", EncodeUint32(8, 0x017e)); +} + +TEST(HpackOutputStreamTest, ThreeByteIntegersEightBitPrefix) { + // Minimum. + EXPECT_EQ("\xff\x80\x01", EncodeUint32(8, 0x017f)); + EXPECT_EQ("\xff\x80\x1e", EncodeUint32(8, 0x0fff)); + // Maximum. + EXPECT_EQ("\xff\xff\x7f", EncodeUint32(8, 0x40fe)); +} + +TEST(HpackOutputStreamTest, FourByteIntegersEightBitPrefix) { + // Minimum. + EXPECT_EQ("\xff\x80\x80\x01", EncodeUint32(8, 0x40ff)); + EXPECT_EQ("\xff\x80\xfe\x03", EncodeUint32(8, 0xffff)); + // Maximum. + EXPECT_EQ("\xff\xff\xff\x7f", EncodeUint32(8, 0x002000fe)); +} + +TEST(HpackOutputStreamTest, FiveByteIntegersEightBitPrefix) { + // Minimum. + EXPECT_EQ("\xff\x80\x80\x80\x01", EncodeUint32(8, 0x002000ff)); + EXPECT_EQ("\xff\x80\xfe\xff\x07", EncodeUint32(8, 0x00ffffff)); + // Maximum. + EXPECT_EQ("\xff\xff\xff\xff\x7f", EncodeUint32(8, 0x100000fe)); +} + +TEST(HpackOutputStreamTest, SixByteIntegersEightBitPrefix) { + // Minimum. + EXPECT_EQ("\xff\x80\x80\x80\x80\x01", EncodeUint32(8, 0x100000ff)); + // Maximum. + EXPECT_EQ("\xff\x80\xfe\xff\xff\x0f", EncodeUint32(8, 0xffffffff)); +} + +// The {Number}ByteIntegersOneToSevenBitPrefix tests below test that +// certain integers are encoded correctly with an N-bit prefix in +// exactly {Number} bytes for N in {1, 2, ..., 7}. + +TEST(HpackOutputStreamTest, OneByteIntegersOneToSevenBitPrefixes) { + // Minimums. + EXPECT_EQ(SpdyString("\x00", 1), EncodeUint32(7, 0x00)); + EXPECT_EQ(SpdyString("\x00", 1), EncodeUint32(6, 0x00)); + EXPECT_EQ(SpdyString("\x00", 1), EncodeUint32(5, 0x00)); + EXPECT_EQ(SpdyString("\x00", 1), EncodeUint32(4, 0x00)); + EXPECT_EQ(SpdyString("\x00", 1), EncodeUint32(3, 0x00)); + EXPECT_EQ(SpdyString("\x00", 1), EncodeUint32(2, 0x00)); + EXPECT_EQ(SpdyString("\x00", 1), EncodeUint32(1, 0x00)); + + // Maximums. + EXPECT_EQ("\x7e", EncodeUint32(7, 0x7e)); + EXPECT_EQ("\x3e", EncodeUint32(6, 0x3e)); + EXPECT_EQ("\x1e", EncodeUint32(5, 0x1e)); + EXPECT_EQ("\x0e", EncodeUint32(4, 0x0e)); + EXPECT_EQ("\x06", EncodeUint32(3, 0x06)); + EXPECT_EQ("\x02", EncodeUint32(2, 0x02)); + EXPECT_EQ(SpdyString("\x00", 1), EncodeUint32(1, 0x00)); +} + +TEST(HpackOutputStreamTest, TwoByteIntegersOneToSevenBitPrefixes) { + // Minimums. + EXPECT_EQ(SpdyString("\x7f\x00", 2), EncodeUint32(7, 0x7f)); + EXPECT_EQ(SpdyString("\x3f\x00", 2), EncodeUint32(6, 0x3f)); + EXPECT_EQ(SpdyString("\x1f\x00", 2), EncodeUint32(5, 0x1f)); + EXPECT_EQ(SpdyString("\x0f\x00", 2), EncodeUint32(4, 0x0f)); + EXPECT_EQ(SpdyString("\x07\x00", 2), EncodeUint32(3, 0x07)); + EXPECT_EQ(SpdyString("\x03\x00", 2), EncodeUint32(2, 0x03)); + EXPECT_EQ(SpdyString("\x01\x00", 2), EncodeUint32(1, 0x01)); + + // Maximums. + EXPECT_EQ("\x7f\x7f", EncodeUint32(7, 0xfe)); + EXPECT_EQ("\x3f\x7f", EncodeUint32(6, 0xbe)); + EXPECT_EQ("\x1f\x7f", EncodeUint32(5, 0x9e)); + EXPECT_EQ("\x0f\x7f", EncodeUint32(4, 0x8e)); + EXPECT_EQ("\x07\x7f", EncodeUint32(3, 0x86)); + EXPECT_EQ("\x03\x7f", EncodeUint32(2, 0x82)); + EXPECT_EQ("\x01\x7f", EncodeUint32(1, 0x80)); +} + +TEST(HpackOutputStreamTest, ThreeByteIntegersOneToSevenBitPrefixes) { + // Minimums. + EXPECT_EQ("\x7f\x80\x01", EncodeUint32(7, 0xff)); + EXPECT_EQ("\x3f\x80\x01", EncodeUint32(6, 0xbf)); + EXPECT_EQ("\x1f\x80\x01", EncodeUint32(5, 0x9f)); + EXPECT_EQ("\x0f\x80\x01", EncodeUint32(4, 0x8f)); + EXPECT_EQ("\x07\x80\x01", EncodeUint32(3, 0x87)); + EXPECT_EQ("\x03\x80\x01", EncodeUint32(2, 0x83)); + EXPECT_EQ("\x01\x80\x01", EncodeUint32(1, 0x81)); + + // Maximums. + EXPECT_EQ("\x7f\xff\x7f", EncodeUint32(7, 0x407e)); + EXPECT_EQ("\x3f\xff\x7f", EncodeUint32(6, 0x403e)); + EXPECT_EQ("\x1f\xff\x7f", EncodeUint32(5, 0x401e)); + EXPECT_EQ("\x0f\xff\x7f", EncodeUint32(4, 0x400e)); + EXPECT_EQ("\x07\xff\x7f", EncodeUint32(3, 0x4006)); + EXPECT_EQ("\x03\xff\x7f", EncodeUint32(2, 0x4002)); + EXPECT_EQ("\x01\xff\x7f", EncodeUint32(1, 0x4000)); +} + +TEST(HpackOutputStreamTest, FourByteIntegersOneToSevenBitPrefixes) { + // Minimums. + EXPECT_EQ("\x7f\x80\x80\x01", EncodeUint32(7, 0x407f)); + EXPECT_EQ("\x3f\x80\x80\x01", EncodeUint32(6, 0x403f)); + EXPECT_EQ("\x1f\x80\x80\x01", EncodeUint32(5, 0x401f)); + EXPECT_EQ("\x0f\x80\x80\x01", EncodeUint32(4, 0x400f)); + EXPECT_EQ("\x07\x80\x80\x01", EncodeUint32(3, 0x4007)); + EXPECT_EQ("\x03\x80\x80\x01", EncodeUint32(2, 0x4003)); + EXPECT_EQ("\x01\x80\x80\x01", EncodeUint32(1, 0x4001)); + + // Maximums. + EXPECT_EQ("\x7f\xff\xff\x7f", EncodeUint32(7, 0x20007e)); + EXPECT_EQ("\x3f\xff\xff\x7f", EncodeUint32(6, 0x20003e)); + EXPECT_EQ("\x1f\xff\xff\x7f", EncodeUint32(5, 0x20001e)); + EXPECT_EQ("\x0f\xff\xff\x7f", EncodeUint32(4, 0x20000e)); + EXPECT_EQ("\x07\xff\xff\x7f", EncodeUint32(3, 0x200006)); + EXPECT_EQ("\x03\xff\xff\x7f", EncodeUint32(2, 0x200002)); + EXPECT_EQ("\x01\xff\xff\x7f", EncodeUint32(1, 0x200000)); +} + +TEST(HpackOutputStreamTest, FiveByteIntegersOneToSevenBitPrefixes) { + // Minimums. + EXPECT_EQ("\x7f\x80\x80\x80\x01", EncodeUint32(7, 0x20007f)); + EXPECT_EQ("\x3f\x80\x80\x80\x01", EncodeUint32(6, 0x20003f)); + EXPECT_EQ("\x1f\x80\x80\x80\x01", EncodeUint32(5, 0x20001f)); + EXPECT_EQ("\x0f\x80\x80\x80\x01", EncodeUint32(4, 0x20000f)); + EXPECT_EQ("\x07\x80\x80\x80\x01", EncodeUint32(3, 0x200007)); + EXPECT_EQ("\x03\x80\x80\x80\x01", EncodeUint32(2, 0x200003)); + EXPECT_EQ("\x01\x80\x80\x80\x01", EncodeUint32(1, 0x200001)); + + // Maximums. + EXPECT_EQ("\x7f\xff\xff\xff\x7f", EncodeUint32(7, 0x1000007e)); + EXPECT_EQ("\x3f\xff\xff\xff\x7f", EncodeUint32(6, 0x1000003e)); + EXPECT_EQ("\x1f\xff\xff\xff\x7f", EncodeUint32(5, 0x1000001e)); + EXPECT_EQ("\x0f\xff\xff\xff\x7f", EncodeUint32(4, 0x1000000e)); + EXPECT_EQ("\x07\xff\xff\xff\x7f", EncodeUint32(3, 0x10000006)); + EXPECT_EQ("\x03\xff\xff\xff\x7f", EncodeUint32(2, 0x10000002)); + EXPECT_EQ("\x01\xff\xff\xff\x7f", EncodeUint32(1, 0x10000000)); +} + +TEST(HpackOutputStreamTest, SixByteIntegersOneToSevenBitPrefixes) { + // Minimums. + EXPECT_EQ("\x7f\x80\x80\x80\x80\x01", EncodeUint32(7, 0x1000007f)); + EXPECT_EQ("\x3f\x80\x80\x80\x80\x01", EncodeUint32(6, 0x1000003f)); + EXPECT_EQ("\x1f\x80\x80\x80\x80\x01", EncodeUint32(5, 0x1000001f)); + EXPECT_EQ("\x0f\x80\x80\x80\x80\x01", EncodeUint32(4, 0x1000000f)); + EXPECT_EQ("\x07\x80\x80\x80\x80\x01", EncodeUint32(3, 0x10000007)); + EXPECT_EQ("\x03\x80\x80\x80\x80\x01", EncodeUint32(2, 0x10000003)); + EXPECT_EQ("\x01\x80\x80\x80\x80\x01", EncodeUint32(1, 0x10000001)); + + // Maximums. + EXPECT_EQ("\x7f\x80\xff\xff\xff\x0f", EncodeUint32(7, 0xffffffff)); + EXPECT_EQ("\x3f\xc0\xff\xff\xff\x0f", EncodeUint32(6, 0xffffffff)); + EXPECT_EQ("\x1f\xe0\xff\xff\xff\x0f", EncodeUint32(5, 0xffffffff)); + EXPECT_EQ("\x0f\xf0\xff\xff\xff\x0f", EncodeUint32(4, 0xffffffff)); + EXPECT_EQ("\x07\xf8\xff\xff\xff\x0f", EncodeUint32(3, 0xffffffff)); + EXPECT_EQ("\x03\xfc\xff\xff\xff\x0f", EncodeUint32(2, 0xffffffff)); + EXPECT_EQ("\x01\xfe\xff\xff\xff\x0f", EncodeUint32(1, 0xffffffff)); +} + +// Test that encoding an integer with an N-bit prefix preserves the +// upper (8-N) bits of the first byte. +TEST(HpackOutputStreamTest, AppendUint32PreservesUpperBits) { + HpackOutputStream output_stream; + output_stream.AppendBits(0x7f, 7); + output_stream.AppendUint32(0x01); + SpdyString str; + output_stream.TakeString(&str); + EXPECT_EQ(SpdyString("\xff\x00", 2), str); +} + +TEST(HpackOutputStreamTest, AppendBytes) { + HpackOutputStream output_stream; + + output_stream.AppendBytes("buffer1"); + output_stream.AppendBytes("buffer2"); + + SpdyString str; + output_stream.TakeString(&str); + EXPECT_EQ("buffer1buffer2", str); +} + +TEST(HpackOutputStreamTest, BoundedTakeString) { + HpackOutputStream output_stream; + + output_stream.AppendBytes("buffer12"); + output_stream.AppendBytes("buffer456"); + + SpdyString str; + output_stream.BoundedTakeString(9, &str); + EXPECT_EQ("buffer12b", str); + + output_stream.AppendBits(0x7f, 7); + output_stream.AppendUint32(0x11); + output_stream.BoundedTakeString(9, &str); + EXPECT_EQ("uffer456\xff", str); + + output_stream.BoundedTakeString(9, &str); + EXPECT_EQ("\x10", str); +} + +} // namespace + +} // namespace spdy
diff --git a/spdy/core/hpack/hpack_round_trip_test.cc b/spdy/core/hpack/hpack_round_trip_test.cc new file mode 100644 index 0000000..4b3a848 --- /dev/null +++ b/spdy/core/hpack/hpack_round_trip_test.cc
@@ -0,0 +1,227 @@ +// Copyright 2014 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include <cmath> +#include <cstdint> +#include <ctime> +#include <vector> + +#include "testing/gtest/include/gtest/gtest.h" +#include "net/third_party/quiche/src/http2/test_tools/http2_random.h" +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_constants.h" +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_decoder_adapter.h" +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_encoder.h" +#include "net/third_party/quiche/src/spdy/core/spdy_test_utils.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_string.h" + +namespace spdy { +namespace test { + +namespace { + +// Supports testing with the input split at every byte boundary. +enum InputSizeParam { ALL_INPUT, ONE_BYTE, ZERO_THEN_ONE_BYTE }; + +class HpackRoundTripTest : public ::testing::TestWithParam<InputSizeParam> { + protected: + HpackRoundTripTest() : encoder_(ObtainHpackHuffmanTable()), decoder_() {} + + void SetUp() override { + // Use a small table size to tickle eviction handling. + encoder_.ApplyHeaderTableSizeSetting(256); + decoder_.ApplyHeaderTableSizeSetting(256); + } + + bool RoundTrip(const SpdyHeaderBlock& header_set) { + SpdyString encoded; + encoder_.EncodeHeaderSet(header_set, &encoded); + + bool success = true; + if (GetParam() == ALL_INPUT) { + // Pass all the input to the decoder at once. + success = decoder_.HandleControlFrameHeadersData(encoded.data(), + encoded.size()); + } else if (GetParam() == ONE_BYTE) { + // Pass the input to the decoder one byte at a time. + const char* data = encoded.data(); + for (size_t ndx = 0; ndx < encoded.size() && success; ++ndx) { + success = decoder_.HandleControlFrameHeadersData(data + ndx, 1); + } + } else if (GetParam() == ZERO_THEN_ONE_BYTE) { + // Pass the input to the decoder one byte at a time, but before each + // byte pass an empty buffer. + const char* data = encoded.data(); + for (size_t ndx = 0; ndx < encoded.size() && success; ++ndx) { + success = (decoder_.HandleControlFrameHeadersData(data + ndx, 0) && + decoder_.HandleControlFrameHeadersData(data + ndx, 1)); + } + } else { + ADD_FAILURE() << "Unknown param: " << GetParam(); + } + + if (success) { + success = decoder_.HandleControlFrameHeadersComplete(nullptr); + } + + EXPECT_EQ(header_set, decoder_.decoded_block()); + return success; + } + + size_t SampleExponential(size_t mean, size_t sanity_bound) { + return std::min<size_t>(-std::log(random_.RandDouble()) * mean, + sanity_bound); + } + + http2::test::Http2Random random_; + HpackEncoder encoder_; + HpackDecoderAdapter decoder_; +}; + +INSTANTIATE_TEST_CASE_P(Tests, + HpackRoundTripTest, + ::testing::Values(ALL_INPUT, + ONE_BYTE, + ZERO_THEN_ONE_BYTE)); + +TEST_P(HpackRoundTripTest, ResponseFixtures) { + { + SpdyHeaderBlock headers; + headers[":status"] = "302"; + headers["cache-control"] = "private"; + headers["date"] = "Mon, 21 Oct 2013 20:13:21 GMT"; + headers["location"] = "https://www.example.com"; + EXPECT_TRUE(RoundTrip(headers)); + } + { + SpdyHeaderBlock headers; + headers[":status"] = "200"; + headers["cache-control"] = "private"; + headers["date"] = "Mon, 21 Oct 2013 20:13:21 GMT"; + headers["location"] = "https://www.example.com"; + EXPECT_TRUE(RoundTrip(headers)); + } + { + SpdyHeaderBlock headers; + headers[":status"] = "200"; + headers["cache-control"] = "private"; + headers["content-encoding"] = "gzip"; + headers["date"] = "Mon, 21 Oct 2013 20:13:22 GMT"; + headers["location"] = "https://www.example.com"; + headers["set-cookie"] = + "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU;" + " max-age=3600; version=1"; + headers["multivalue"] = SpdyString("foo\0bar", 7); + EXPECT_TRUE(RoundTrip(headers)); + } +} + +TEST_P(HpackRoundTripTest, RequestFixtures) { + { + SpdyHeaderBlock headers; + headers[":authority"] = "www.example.com"; + headers[":method"] = "GET"; + headers[":path"] = "/"; + headers[":scheme"] = "http"; + headers["cookie"] = "baz=bing; foo=bar"; + EXPECT_TRUE(RoundTrip(headers)); + } + { + SpdyHeaderBlock headers; + headers[":authority"] = "www.example.com"; + headers[":method"] = "GET"; + headers[":path"] = "/"; + headers[":scheme"] = "http"; + headers["cache-control"] = "no-cache"; + headers["cookie"] = "foo=bar; spam=eggs"; + EXPECT_TRUE(RoundTrip(headers)); + } + { + SpdyHeaderBlock headers; + headers[":authority"] = "www.example.com"; + headers[":method"] = "GET"; + headers[":path"] = "/index.html"; + headers[":scheme"] = "https"; + headers["custom-key"] = "custom-value"; + headers["cookie"] = "baz=bing; fizzle=fazzle; garbage"; + headers["multivalue"] = SpdyString("foo\0bar", 7); + EXPECT_TRUE(RoundTrip(headers)); + } +} + +TEST_P(HpackRoundTripTest, RandomizedExamples) { + // Grow vectors of names & values, which are seeded with fixtures and then + // expanded with dynamically generated data. Samples are taken using the + // exponential distribution. + std::vector<SpdyString> pseudo_header_names, random_header_names; + pseudo_header_names.push_back(":authority"); + pseudo_header_names.push_back(":path"); + pseudo_header_names.push_back(":status"); + + // TODO(jgraettinger): Enable "cookie" as a name fixture. Crumbs may be + // reconstructed in any order, which breaks the simple validation used here. + + std::vector<SpdyString> values; + values.push_back("/"); + values.push_back("/index.html"); + values.push_back("200"); + values.push_back("404"); + values.push_back(""); + values.push_back("baz=bing; foo=bar; garbage"); + values.push_back("baz=bing; fizzle=fazzle; garbage"); + + for (size_t i = 0; i != 2000; ++i) { + SpdyHeaderBlock headers; + + // Choose a random number of headers to add, and of these a random subset + // will be HTTP/2 pseudo headers. + size_t header_count = 1 + SampleExponential(7, 50); + size_t pseudo_header_count = + std::min(header_count, 1 + SampleExponential(7, 50)); + EXPECT_LE(pseudo_header_count, header_count); + for (size_t j = 0; j != header_count; ++j) { + SpdyString name, value; + // Pseudo headers must be added before regular headers. + if (j < pseudo_header_count) { + // Choose one of the defined pseudo headers at random. + size_t name_index = random_.Uniform(pseudo_header_names.size()); + name = pseudo_header_names[name_index]; + } else { + // Randomly reuse an existing header name, or generate a new one. + size_t name_index = SampleExponential(20, 200); + if (name_index >= random_header_names.size()) { + name = random_.RandString(1 + SampleExponential(5, 30)); + // A regular header cannot begin with the pseudo header prefix ":". + if (name[0] == ':') { + name[0] = 'x'; + } + random_header_names.push_back(name); + } else { + name = random_header_names[name_index]; + } + } + + // Randomly reuse an existing value, or generate a new one. + size_t value_index = SampleExponential(20, 200); + if (value_index >= values.size()) { + SpdyString newvalue = random_.RandString(1 + SampleExponential(15, 75)); + // Currently order is not preserved in the encoder. In particular, + // when a value is decomposed at \0 delimiters, its parts might get + // encoded out of order if some but not all of them already exist in + // the header table. For now, avoid \0 bytes in values. + std::replace(newvalue.begin(), newvalue.end(), '\x00', '\x01'); + values.push_back(newvalue); + value = values.back(); + } else { + value = values[value_index]; + } + headers[name] = value; + } + EXPECT_TRUE(RoundTrip(headers)); + } +} + +} // namespace + +} // namespace test +} // namespace spdy
diff --git a/spdy/core/hpack/hpack_static_table.cc b/spdy/core/hpack/hpack_static_table.cc new file mode 100644 index 0000000..14e282e --- /dev/null +++ b/spdy/core/hpack/hpack_static_table.cc
@@ -0,0 +1,50 @@ +// Copyright 2014 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_static_table.h" + +#include "base/logging.h" +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_constants.h" +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_entry.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_estimate_memory_usage.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_string_piece.h" + +namespace spdy { + +HpackStaticTable::HpackStaticTable() = default; + +HpackStaticTable::~HpackStaticTable() = default; + +void HpackStaticTable::Initialize(const HpackStaticEntry* static_entry_table, + size_t static_entry_count) { + CHECK(!IsInitialized()); + + int total_insertions = 0; + for (const HpackStaticEntry* it = static_entry_table; + it != static_entry_table + static_entry_count; ++it) { + static_entries_.push_back( + HpackEntry(SpdyStringPiece(it->name, it->name_len), + SpdyStringPiece(it->value, it->value_len), + true, // is_static + total_insertions)); + HpackEntry* entry = &static_entries_.back(); + CHECK(static_index_.insert(entry).second); + // Multiple static entries may have the same name, so inserts may fail. + static_name_index_.insert(std::make_pair(entry->name(), entry)); + + ++total_insertions; + } +} + +bool HpackStaticTable::IsInitialized() const { + return !static_entries_.empty(); +} + +size_t HpackStaticTable::EstimateMemoryUsage() const { + return SpdyEstimateMemoryUsage(static_entries_) + + SpdyEstimateMemoryUsage(static_index_) + + SpdyEstimateMemoryUsage(static_name_index_); +} + +} // namespace spdy
diff --git a/spdy/core/hpack/hpack_static_table.h b/spdy/core/hpack/hpack_static_table.h new file mode 100644 index 0000000..f354a12 --- /dev/null +++ b/spdy/core/hpack/hpack_static_table.h
@@ -0,0 +1,54 @@ +// Copyright 2014 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#ifndef QUICHE_SPDY_CORE_HPACK_HPACK_STATIC_TABLE_H_ +#define QUICHE_SPDY_CORE_HPACK_HPACK_STATIC_TABLE_H_ + +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_header_table.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_export.h" + +namespace spdy { + +struct HpackStaticEntry; + +// HpackStaticTable provides |static_entries_| and |static_index_| for HPACK +// encoding and decoding contexts. Once initialized, an instance is read only +// and may be accessed only through its const interface. Such an instance may +// be shared accross multiple HPACK contexts. +class SPDY_EXPORT_PRIVATE HpackStaticTable { + public: + HpackStaticTable(); + ~HpackStaticTable(); + + // Prepares HpackStaticTable by filling up static_entries_ and static_index_ + // from an array of struct HpackStaticEntry. Must be called exactly once. + void Initialize(const HpackStaticEntry* static_entry_table, + size_t static_entry_count); + + // Returns whether Initialize() has been called. + bool IsInitialized() const; + + // Accessors. + const HpackHeaderTable::EntryTable& GetStaticEntries() const { + return static_entries_; + } + const HpackHeaderTable::UnorderedEntrySet& GetStaticIndex() const { + return static_index_; + } + const HpackHeaderTable::NameToEntryMap& GetStaticNameIndex() const { + return static_name_index_; + } + + // Returns the estimate of dynamically allocated memory in bytes. + size_t EstimateMemoryUsage() const; + + private: + HpackHeaderTable::EntryTable static_entries_; + HpackHeaderTable::UnorderedEntrySet static_index_; + HpackHeaderTable::NameToEntryMap static_name_index_; +}; + +} // namespace spdy + +#endif // QUICHE_SPDY_CORE_HPACK_HPACK_STATIC_TABLE_H_
diff --git a/spdy/core/hpack/hpack_static_table_test.cc b/spdy/core/hpack/hpack_static_table_test.cc new file mode 100644 index 0000000..4550be0 --- /dev/null +++ b/spdy/core/hpack/hpack_static_table_test.cc
@@ -0,0 +1,60 @@ +// Copyright 2014 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_static_table.h" + +#include <set> +#include <vector> + +#include "testing/gtest/include/gtest/gtest.h" +#include "net/third_party/quiche/src/spdy/core/hpack/hpack_constants.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_string_piece.h" + +namespace spdy { + +namespace test { + +namespace { + +class HpackStaticTableTest : public ::testing::Test { + protected: + HpackStaticTableTest() : table_() {} + + HpackStaticTable table_; +}; + +// Check that an initialized instance has the right number of entries. +TEST_F(HpackStaticTableTest, Initialize) { + EXPECT_FALSE(table_.IsInitialized()); + table_.Initialize(HpackStaticTableVector().data(), + HpackStaticTableVector().size()); + EXPECT_TRUE(table_.IsInitialized()); + + HpackHeaderTable::EntryTable static_entries = table_.GetStaticEntries(); + EXPECT_EQ(HpackStaticTableVector().size(), static_entries.size()); + + HpackHeaderTable::UnorderedEntrySet static_index = table_.GetStaticIndex(); + EXPECT_EQ(HpackStaticTableVector().size(), static_index.size()); + + HpackHeaderTable::NameToEntryMap static_name_index = + table_.GetStaticNameIndex(); + std::set<SpdyStringPiece> names; + for (auto* entry : static_index) { + names.insert(entry->name()); + } + EXPECT_EQ(names.size(), static_name_index.size()); +} + +// Test that ObtainHpackStaticTable returns the same instance every time. +TEST_F(HpackStaticTableTest, IsSingleton) { + const HpackStaticTable* static_table_one = &ObtainHpackStaticTable(); + const HpackStaticTable* static_table_two = &ObtainHpackStaticTable(); + EXPECT_EQ(static_table_one, static_table_two); +} + +} // namespace + +} // namespace test + +} // namespace spdy