1 /* 2 * nghttp2 - HTTP/2 C Library 3 * 4 * Copyright (c) 2013 Tatsuhiro Tsujikawa 5 * 6 * Permission is hereby granted, free of charge, to any person obtaining 7 * a copy of this software and associated documentation files (the 8 * "Software"), to deal in the Software without restriction, including 9 * without limitation the rights to use, copy, modify, merge, publish, 10 * distribute, sublicense, and/or sell copies of the Software, and to 11 * permit persons to whom the Software is furnished to do so, subject to 12 * the following conditions: 13 * 14 * The above copyright notice and this permission notice shall be 15 * included in all copies or substantial portions of the Software. 16 * 17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 19 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 20 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 21 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 22 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 23 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 24 */ 25 #ifndef NGHTTP2_HD_H 26 #define NGHTTP2_HD_H 27 28 #ifdef HAVE_CONFIG_H 29 #include <config.h> 30 #endif /* HAVE_CONFIG_H */ 31 32 #include "nghttp2.h" 33 34 #include "nghttp2_hd_huffman.h" 35 #include "nghttp2_buf.h" 36 #include "nghttp2_mem.h" 37 #include "nghttp2_rcbuf.h" 38 39 #define NGHTTP2_HD_DEFAULT_MAX_BUFFER_SIZE NGHTTP2_DEFAULT_HEADER_TABLE_SIZE 40 #define NGHTTP2_HD_ENTRY_OVERHEAD 32 41 42 /* The maximum length of one name/value pair. This is the sum of the 43 length of name and value. This is not specified by the spec. We 44 just chose the arbitrary size */ 45 #define NGHTTP2_HD_MAX_NV 65536 46 47 /* Default size of maximum table buffer size for encoder. Even if 48 remote decoder notifies larger buffer size for its decoding, 49 encoder only uses the memory up to this value. */ 50 #define NGHTTP2_HD_DEFAULT_MAX_DEFLATE_BUFFER_SIZE (1 << 12) 51 52 /* Exported for unit test */ 53 #define NGHTTP2_STATIC_TABLE_LENGTH 61 54 55 /* Generated by genlibtokenlookup.py */ 56 typedef enum { 57 NGHTTP2_TOKEN__AUTHORITY = 0, 58 NGHTTP2_TOKEN__METHOD = 1, 59 NGHTTP2_TOKEN__PATH = 3, 60 NGHTTP2_TOKEN__SCHEME = 5, 61 NGHTTP2_TOKEN__STATUS = 7, 62 NGHTTP2_TOKEN_ACCEPT_CHARSET = 14, 63 NGHTTP2_TOKEN_ACCEPT_ENCODING = 15, 64 NGHTTP2_TOKEN_ACCEPT_LANGUAGE = 16, 65 NGHTTP2_TOKEN_ACCEPT_RANGES = 17, 66 NGHTTP2_TOKEN_ACCEPT = 18, 67 NGHTTP2_TOKEN_ACCESS_CONTROL_ALLOW_ORIGIN = 19, 68 NGHTTP2_TOKEN_AGE = 20, 69 NGHTTP2_TOKEN_ALLOW = 21, 70 NGHTTP2_TOKEN_AUTHORIZATION = 22, 71 NGHTTP2_TOKEN_CACHE_CONTROL = 23, 72 NGHTTP2_TOKEN_CONTENT_DISPOSITION = 24, 73 NGHTTP2_TOKEN_CONTENT_ENCODING = 25, 74 NGHTTP2_TOKEN_CONTENT_LANGUAGE = 26, 75 NGHTTP2_TOKEN_CONTENT_LENGTH = 27, 76 NGHTTP2_TOKEN_CONTENT_LOCATION = 28, 77 NGHTTP2_TOKEN_CONTENT_RANGE = 29, 78 NGHTTP2_TOKEN_CONTENT_TYPE = 30, 79 NGHTTP2_TOKEN_COOKIE = 31, 80 NGHTTP2_TOKEN_DATE = 32, 81 NGHTTP2_TOKEN_ETAG = 33, 82 NGHTTP2_TOKEN_EXPECT = 34, 83 NGHTTP2_TOKEN_EXPIRES = 35, 84 NGHTTP2_TOKEN_FROM = 36, 85 NGHTTP2_TOKEN_HOST = 37, 86 NGHTTP2_TOKEN_IF_MATCH = 38, 87 NGHTTP2_TOKEN_IF_MODIFIED_SINCE = 39, 88 NGHTTP2_TOKEN_IF_NONE_MATCH = 40, 89 NGHTTP2_TOKEN_IF_RANGE = 41, 90 NGHTTP2_TOKEN_IF_UNMODIFIED_SINCE = 42, 91 NGHTTP2_TOKEN_LAST_MODIFIED = 43, 92 NGHTTP2_TOKEN_LINK = 44, 93 NGHTTP2_TOKEN_LOCATION = 45, 94 NGHTTP2_TOKEN_MAX_FORWARDS = 46, 95 NGHTTP2_TOKEN_PROXY_AUTHENTICATE = 47, 96 NGHTTP2_TOKEN_PROXY_AUTHORIZATION = 48, 97 NGHTTP2_TOKEN_RANGE = 49, 98 NGHTTP2_TOKEN_REFERER = 50, 99 NGHTTP2_TOKEN_REFRESH = 51, 100 NGHTTP2_TOKEN_RETRY_AFTER = 52, 101 NGHTTP2_TOKEN_SERVER = 53, 102 NGHTTP2_TOKEN_SET_COOKIE = 54, 103 NGHTTP2_TOKEN_STRICT_TRANSPORT_SECURITY = 55, 104 NGHTTP2_TOKEN_TRANSFER_ENCODING = 56, 105 NGHTTP2_TOKEN_USER_AGENT = 57, 106 NGHTTP2_TOKEN_VARY = 58, 107 NGHTTP2_TOKEN_VIA = 59, 108 NGHTTP2_TOKEN_WWW_AUTHENTICATE = 60, 109 NGHTTP2_TOKEN_TE, 110 NGHTTP2_TOKEN_CONNECTION, 111 NGHTTP2_TOKEN_KEEP_ALIVE, 112 NGHTTP2_TOKEN_PROXY_CONNECTION, 113 NGHTTP2_TOKEN_UPGRADE, 114 } nghttp2_token; 115 116 struct nghttp2_hd_entry; 117 typedef struct nghttp2_hd_entry nghttp2_hd_entry; 118 119 typedef struct { 120 /* The buffer containing header field name. NULL-termination is 121 guaranteed. */ 122 nghttp2_rcbuf *name; 123 /* The buffer containing header field value. NULL-termination is 124 guaranteed. */ 125 nghttp2_rcbuf *value; 126 /* nghttp2_token value for name. It could be -1 if we have no token 127 for that header field name. */ 128 int32_t token; 129 /* Bitwise OR of one or more of nghttp2_nv_flag. */ 130 uint8_t flags; 131 } nghttp2_hd_nv; 132 133 struct nghttp2_hd_entry { 134 /* The header field name/value pair */ 135 nghttp2_hd_nv nv; 136 /* This is solely for nghttp2_hd_{deflate,inflate}_get_table_entry 137 APIs to keep backward compatibility. */ 138 nghttp2_nv cnv; 139 /* The next entry which shares same bucket in hash table. */ 140 nghttp2_hd_entry *next; 141 /* The sequence number. We will increment it by one whenever we 142 store nghttp2_hd_entry to dynamic header table. */ 143 uint32_t seq; 144 /* The hash value for header name (nv.name). */ 145 uint32_t hash; 146 }; 147 148 /* The entry used for static header table. */ 149 typedef struct { 150 nghttp2_rcbuf name; 151 nghttp2_rcbuf value; 152 nghttp2_nv cnv; 153 int32_t token; 154 uint32_t hash; 155 } nghttp2_hd_static_entry; 156 157 typedef struct { 158 nghttp2_hd_entry **buffer; 159 size_t mask; 160 size_t first; 161 size_t len; 162 } nghttp2_hd_ringbuf; 163 164 typedef enum { 165 NGHTTP2_HD_OPCODE_NONE, 166 NGHTTP2_HD_OPCODE_INDEXED, 167 NGHTTP2_HD_OPCODE_NEWNAME, 168 NGHTTP2_HD_OPCODE_INDNAME 169 } nghttp2_hd_opcode; 170 171 typedef enum { 172 NGHTTP2_HD_STATE_EXPECT_TABLE_SIZE, 173 NGHTTP2_HD_STATE_INFLATE_START, 174 NGHTTP2_HD_STATE_OPCODE, 175 NGHTTP2_HD_STATE_READ_TABLE_SIZE, 176 NGHTTP2_HD_STATE_READ_INDEX, 177 NGHTTP2_HD_STATE_NEWNAME_CHECK_NAMELEN, 178 NGHTTP2_HD_STATE_NEWNAME_READ_NAMELEN, 179 NGHTTP2_HD_STATE_NEWNAME_READ_NAMEHUFF, 180 NGHTTP2_HD_STATE_NEWNAME_READ_NAME, 181 NGHTTP2_HD_STATE_CHECK_VALUELEN, 182 NGHTTP2_HD_STATE_READ_VALUELEN, 183 NGHTTP2_HD_STATE_READ_VALUEHUFF, 184 NGHTTP2_HD_STATE_READ_VALUE 185 } nghttp2_hd_inflate_state; 186 187 typedef enum { 188 NGHTTP2_HD_WITH_INDEXING, 189 NGHTTP2_HD_WITHOUT_INDEXING, 190 NGHTTP2_HD_NEVER_INDEXING 191 } nghttp2_hd_indexing_mode; 192 193 typedef struct { 194 /* dynamic header table */ 195 nghttp2_hd_ringbuf hd_table; 196 /* Memory allocator */ 197 nghttp2_mem *mem; 198 /* Abstract buffer size of hd_table as described in the spec. This 199 is the sum of length of name/value in hd_table + 200 NGHTTP2_HD_ENTRY_OVERHEAD bytes overhead per each entry. */ 201 size_t hd_table_bufsize; 202 /* The effective header table size. */ 203 size_t hd_table_bufsize_max; 204 /* Next sequence number for nghttp2_hd_entry */ 205 uint32_t next_seq; 206 /* If inflate/deflate error occurred, this value is set to 1 and 207 further invocation of inflate/deflate will fail with 208 NGHTTP2_ERR_HEADER_COMP. */ 209 uint8_t bad; 210 } nghttp2_hd_context; 211 212 #define HD_MAP_SIZE 128 213 214 typedef struct { 215 nghttp2_hd_entry *table[HD_MAP_SIZE]; 216 } nghttp2_hd_map; 217 218 struct nghttp2_hd_deflater { 219 nghttp2_hd_context ctx; 220 nghttp2_hd_map map; 221 /* The upper limit of the header table size the deflater accepts. */ 222 size_t deflate_hd_table_bufsize_max; 223 /* Minimum header table size notified in the next context update */ 224 size_t min_hd_table_bufsize_max; 225 /* If nonzero, send header table size using encoding context update 226 in the next deflate process */ 227 uint8_t notify_table_size_change; 228 }; 229 230 struct nghttp2_hd_inflater { 231 nghttp2_hd_context ctx; 232 /* Stores current state of huffman decoding */ 233 nghttp2_hd_huff_decode_context huff_decode_ctx; 234 /* header buffer */ 235 nghttp2_buf namebuf, valuebuf; 236 nghttp2_rcbuf *namercbuf, *valuercbuf; 237 /* Pointer to the name/value pair which are used in the current 238 header emission. */ 239 nghttp2_rcbuf *nv_name_keep, *nv_value_keep; 240 /* The number of bytes to read */ 241 size_t left; 242 /* The index in indexed repr or indexed name */ 243 size_t index; 244 /* The maximum header table size the inflater supports. This is the 245 same value transmitted in SETTINGS_HEADER_TABLE_SIZE */ 246 size_t settings_hd_table_bufsize_max; 247 /* Minimum header table size set by nghttp2_hd_inflate_change_table_size */ 248 size_t min_hd_table_bufsize_max; 249 /* The number of next shift to decode integer */ 250 size_t shift; 251 nghttp2_hd_opcode opcode; 252 nghttp2_hd_inflate_state state; 253 /* nonzero if string is huffman encoded */ 254 uint8_t huffman_encoded; 255 /* nonzero if deflater requires that current entry is indexed */ 256 uint8_t index_required; 257 /* nonzero if deflater requires that current entry must not be 258 indexed */ 259 uint8_t no_index; 260 }; 261 262 /* 263 * Initializes the |ent| members. The reference counts of nv->name 264 * and nv->value are increased by one for each. 265 */ 266 void nghttp2_hd_entry_init(nghttp2_hd_entry *ent, nghttp2_hd_nv *nv); 267 268 /* 269 * This function decreases the reference counts of nv->name and 270 * nv->value. 271 */ 272 void nghttp2_hd_entry_free(nghttp2_hd_entry *ent); 273 274 /* 275 * Initializes |deflater| for deflating name/values pairs. 276 * 277 * The encoder only uses up to 278 * NGHTTP2_HD_DEFAULT_MAX_DEFLATE_BUFFER_SIZE bytes for header table 279 * even if the larger value is specified later in 280 * nghttp2_hd_change_table_size(). 281 * 282 * This function returns 0 if it succeeds, or one of the following 283 * negative error codes: 284 * 285 * NGHTTP2_ERR_NOMEM 286 * Out of memory. 287 */ 288 int nghttp2_hd_deflate_init(nghttp2_hd_deflater *deflater, nghttp2_mem *mem); 289 290 /* 291 * Initializes |deflater| for deflating name/values pairs. 292 * 293 * The encoder only uses up to |max_deflate_dynamic_table_size| bytes 294 * for header table even if the larger value is specified later in 295 * nghttp2_hd_change_table_size(). 296 * 297 * This function returns 0 if it succeeds, or one of the following 298 * negative error codes: 299 * 300 * NGHTTP2_ERR_NOMEM 301 * Out of memory. 302 */ 303 int nghttp2_hd_deflate_init2(nghttp2_hd_deflater *deflater, 304 size_t max_deflate_dynamic_table_size, 305 nghttp2_mem *mem); 306 307 /* 308 * Deallocates any resources allocated for |deflater|. 309 */ 310 void nghttp2_hd_deflate_free(nghttp2_hd_deflater *deflater); 311 312 /* 313 * Deflates the |nva|, which has the |nvlen| name/value pairs, into 314 * the |bufs|. 315 * 316 * This function expands |bufs| as necessary to store the result. If 317 * buffers is full and the process still requires more space, this 318 * function fails and returns NGHTTP2_ERR_HEADER_COMP. 319 * 320 * After this function returns, it is safe to delete the |nva|. 321 * 322 * This function returns 0 if it succeeds, or one of the following 323 * negative error codes: 324 * 325 * NGHTTP2_ERR_NOMEM 326 * Out of memory. 327 * NGHTTP2_ERR_HEADER_COMP 328 * Deflation process has failed. 329 * NGHTTP2_ERR_BUFFER_ERROR 330 * Out of buffer space. 331 */ 332 int nghttp2_hd_deflate_hd_bufs(nghttp2_hd_deflater *deflater, 333 nghttp2_bufs *bufs, const nghttp2_nv *nva, 334 size_t nvlen); 335 336 /* 337 * Initializes |inflater| for inflating name/values pairs. 338 * 339 * This function returns 0 if it succeeds, or one of the following 340 * negative error codes: 341 * 342 * :enum:`NGHTTP2_ERR_NOMEM` 343 * Out of memory. 344 */ 345 int nghttp2_hd_inflate_init(nghttp2_hd_inflater *inflater, nghttp2_mem *mem); 346 347 /* 348 * Deallocates any resources allocated for |inflater|. 349 */ 350 void nghttp2_hd_inflate_free(nghttp2_hd_inflater *inflater); 351 352 /* 353 * Similar to nghttp2_hd_inflate_hd(), but this takes nghttp2_hd_nv 354 * instead of nghttp2_nv as output parameter |nv_out|. Other than 355 * that return values and semantics are the same as 356 * nghttp2_hd_inflate_hd(). 357 */ 358 ssize_t nghttp2_hd_inflate_hd_nv(nghttp2_hd_inflater *inflater, 359 nghttp2_hd_nv *nv_out, int *inflate_flags, 360 const uint8_t *in, size_t inlen, int in_final); 361 362 /* For unittesting purpose */ 363 int nghttp2_hd_emit_indname_block(nghttp2_bufs *bufs, size_t index, 364 nghttp2_nv *nv, int indexing_mode); 365 366 /* For unittesting purpose */ 367 int nghttp2_hd_emit_newname_block(nghttp2_bufs *bufs, nghttp2_nv *nv, 368 int indexing_mode); 369 370 /* For unittesting purpose */ 371 int nghttp2_hd_emit_table_size(nghttp2_bufs *bufs, size_t table_size); 372 373 /* For unittesting purpose */ 374 nghttp2_hd_nv nghttp2_hd_table_get(nghttp2_hd_context *context, size_t index); 375 376 /* For unittesting purpose */ 377 ssize_t nghttp2_hd_decode_length(uint32_t *res, size_t *shift_ptr, int *fin, 378 uint32_t initial, size_t shift, uint8_t *in, 379 uint8_t *last, size_t prefix); 380 381 /* Huffman encoding/decoding functions */ 382 383 /* 384 * Counts the required bytes to encode |src| with length |len|. 385 * 386 * This function returns the number of required bytes to encode given 387 * data, including padding of prefix of terminal symbol code. This 388 * function always succeeds. 389 */ 390 size_t nghttp2_hd_huff_encode_count(const uint8_t *src, size_t len); 391 392 /* 393 * Encodes the given data |src| with length |srclen| to the |bufs|. 394 * This function expands extra buffers in |bufs| if necessary. 395 * 396 * This function returns 0 if it succeeds, or one of the following 397 * negative error codes: 398 * 399 * NGHTTP2_ERR_NOMEM 400 * Out of memory. 401 * NGHTTP2_ERR_BUFFER_ERROR 402 * Out of buffer space. 403 */ 404 int nghttp2_hd_huff_encode(nghttp2_bufs *bufs, const uint8_t *src, 405 size_t srclen); 406 407 void nghttp2_hd_huff_decode_context_init(nghttp2_hd_huff_decode_context *ctx); 408 409 /* 410 * Decodes the given data |src| with length |srclen|. The |ctx| must 411 * be initialized by nghttp2_hd_huff_decode_context_init(). The result 412 * will be written to |buf|. This function assumes that |buf| has the 413 * enough room to store the decoded byte string. 414 * 415 * The caller must set the |fin| to nonzero if the given input is the 416 * final block. 417 * 418 * This function returns the number of read bytes from the |in|. 419 * 420 * If this function fails, it returns one of the following negative 421 * return codes: 422 * 423 * NGHTTP2_ERR_NOMEM 424 * Out of memory. 425 * NGHTTP2_ERR_HEADER_COMP 426 * Decoding process has failed. 427 */ 428 ssize_t nghttp2_hd_huff_decode(nghttp2_hd_huff_decode_context *ctx, 429 nghttp2_buf *buf, const uint8_t *src, 430 size_t srclen, int fin); 431 432 #endif /* NGHTTP2_HD_H */ 433