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/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__PROTOCOL, 115 } nghttp2_token; 116 117 struct nghttp2_hd_entry; 118 typedef struct nghttp2_hd_entry nghttp2_hd_entry; 119 120 typedef struct { 121 /* The buffer containing header field name. NULL-termination is 122 guaranteed. */ 123 nghttp2_rcbuf *name; 124 /* The buffer containing header field value. NULL-termination is 125 guaranteed. */ 126 nghttp2_rcbuf *value; 127 /* nghttp2_token value for name. It could be -1 if we have no token 128 for that header field name. */ 129 int32_t token; 130 /* Bitwise OR of one or more of nghttp2_nv_flag. */ 131 uint8_t flags; 132 } nghttp2_hd_nv; 133 134 struct nghttp2_hd_entry { 135 /* The header field name/value pair */ 136 nghttp2_hd_nv nv; 137 /* This is solely for nghttp2_hd_{deflate,inflate}_get_table_entry 138 APIs to keep backward compatibility. */ 139 nghttp2_nv cnv; 140 /* The next entry which shares same bucket in hash table. */ 141 nghttp2_hd_entry *next; 142 /* The sequence number. We will increment it by one whenever we 143 store nghttp2_hd_entry to dynamic header table. */ 144 uint32_t seq; 145 /* The hash value for header name (nv.name). */ 146 uint32_t hash; 147 }; 148 149 /* The entry used for static header table. */ 150 typedef struct { 151 nghttp2_rcbuf name; 152 nghttp2_rcbuf value; 153 nghttp2_nv cnv; 154 int32_t token; 155 uint32_t hash; 156 } nghttp2_hd_static_entry; 157 158 typedef struct { 159 nghttp2_hd_entry **buffer; 160 size_t mask; 161 size_t first; 162 size_t len; 163 } nghttp2_hd_ringbuf; 164 165 typedef enum { 166 NGHTTP2_HD_OPCODE_NONE, 167 NGHTTP2_HD_OPCODE_INDEXED, 168 NGHTTP2_HD_OPCODE_NEWNAME, 169 NGHTTP2_HD_OPCODE_INDNAME 170 } nghttp2_hd_opcode; 171 172 typedef enum { 173 NGHTTP2_HD_STATE_EXPECT_TABLE_SIZE, 174 NGHTTP2_HD_STATE_INFLATE_START, 175 NGHTTP2_HD_STATE_OPCODE, 176 NGHTTP2_HD_STATE_READ_TABLE_SIZE, 177 NGHTTP2_HD_STATE_READ_INDEX, 178 NGHTTP2_HD_STATE_NEWNAME_CHECK_NAMELEN, 179 NGHTTP2_HD_STATE_NEWNAME_READ_NAMELEN, 180 NGHTTP2_HD_STATE_NEWNAME_READ_NAMEHUFF, 181 NGHTTP2_HD_STATE_NEWNAME_READ_NAME, 182 NGHTTP2_HD_STATE_CHECK_VALUELEN, 183 NGHTTP2_HD_STATE_READ_VALUELEN, 184 NGHTTP2_HD_STATE_READ_VALUEHUFF, 185 NGHTTP2_HD_STATE_READ_VALUE 186 } nghttp2_hd_inflate_state; 187 188 typedef enum { 189 NGHTTP2_HD_WITH_INDEXING, 190 NGHTTP2_HD_WITHOUT_INDEXING, 191 NGHTTP2_HD_NEVER_INDEXING 192 } nghttp2_hd_indexing_mode; 193 194 typedef struct { 195 /* dynamic header table */ 196 nghttp2_hd_ringbuf hd_table; 197 /* Memory allocator */ 198 nghttp2_mem *mem; 199 /* Abstract buffer size of hd_table as described in the spec. This 200 is the sum of length of name/value in hd_table + 201 NGHTTP2_HD_ENTRY_OVERHEAD bytes overhead per each entry. */ 202 size_t hd_table_bufsize; 203 /* The effective header table size. */ 204 size_t hd_table_bufsize_max; 205 /* Next sequence number for nghttp2_hd_entry */ 206 uint32_t next_seq; 207 /* If inflate/deflate error occurred, this value is set to 1 and 208 further invocation of inflate/deflate will fail with 209 NGHTTP2_ERR_HEADER_COMP. */ 210 uint8_t bad; 211 } nghttp2_hd_context; 212 213 #define HD_MAP_SIZE 128 214 215 typedef struct { 216 nghttp2_hd_entry *table[HD_MAP_SIZE]; 217 } nghttp2_hd_map; 218 219 struct nghttp2_hd_deflater { 220 nghttp2_hd_context ctx; 221 nghttp2_hd_map map; 222 /* The upper limit of the header table size the deflater accepts. */ 223 size_t deflate_hd_table_bufsize_max; 224 /* Minimum header table size notified in the next context update */ 225 size_t min_hd_table_bufsize_max; 226 /* If nonzero, send header table size using encoding context update 227 in the next deflate process */ 228 uint8_t notify_table_size_change; 229 }; 230 231 struct nghttp2_hd_inflater { 232 nghttp2_hd_context ctx; 233 /* Stores current state of huffman decoding */ 234 nghttp2_hd_huff_decode_context huff_decode_ctx; 235 /* header buffer */ 236 nghttp2_buf namebuf, valuebuf; 237 nghttp2_rcbuf *namercbuf, *valuercbuf; 238 /* Pointer to the name/value pair which are used in the current 239 header emission. */ 240 nghttp2_rcbuf *nv_name_keep, *nv_value_keep; 241 /* The number of bytes to read */ 242 size_t left; 243 /* The index in indexed repr or indexed name */ 244 size_t index; 245 /* The maximum header table size the inflater supports. This is the 246 same value transmitted in SETTINGS_HEADER_TABLE_SIZE */ 247 size_t settings_hd_table_bufsize_max; 248 /* Minimum header table size set by nghttp2_hd_inflate_change_table_size */ 249 size_t min_hd_table_bufsize_max; 250 /* The number of next shift to decode integer */ 251 size_t shift; 252 nghttp2_hd_opcode opcode; 253 nghttp2_hd_inflate_state state; 254 /* nonzero if string is huffman encoded */ 255 uint8_t huffman_encoded; 256 /* nonzero if deflater requires that current entry is indexed */ 257 uint8_t index_required; 258 /* nonzero if deflater requires that current entry must not be 259 indexed */ 260 uint8_t no_index; 261 }; 262 263 /* 264 * Initializes the |ent| members. The reference counts of nv->name 265 * and nv->value are increased by one for each. 266 */ 267 void nghttp2_hd_entry_init(nghttp2_hd_entry *ent, nghttp2_hd_nv *nv); 268 269 /* 270 * This function decreases the reference counts of nv->name and 271 * nv->value. 272 */ 273 void nghttp2_hd_entry_free(nghttp2_hd_entry *ent); 274 275 /* 276 * Initializes |deflater| for deflating name/values pairs. 277 * 278 * The encoder only uses up to 279 * NGHTTP2_HD_DEFAULT_MAX_DEFLATE_BUFFER_SIZE bytes for header table 280 * even if the larger value is specified later in 281 * nghttp2_hd_change_table_size(). 282 * 283 * This function returns 0 if it succeeds, or one of the following 284 * negative error codes: 285 * 286 * NGHTTP2_ERR_NOMEM 287 * Out of memory. 288 */ 289 int nghttp2_hd_deflate_init(nghttp2_hd_deflater *deflater, nghttp2_mem *mem); 290 291 /* 292 * Initializes |deflater| for deflating name/values pairs. 293 * 294 * The encoder only uses up to |max_deflate_dynamic_table_size| bytes 295 * for header table even if the larger value is specified later in 296 * nghttp2_hd_change_table_size(). 297 * 298 * This function returns 0 if it succeeds, or one of the following 299 * negative error codes: 300 * 301 * NGHTTP2_ERR_NOMEM 302 * Out of memory. 303 */ 304 int nghttp2_hd_deflate_init2(nghttp2_hd_deflater *deflater, 305 size_t max_deflate_dynamic_table_size, 306 nghttp2_mem *mem); 307 308 /* 309 * Deallocates any resources allocated for |deflater|. 310 */ 311 void nghttp2_hd_deflate_free(nghttp2_hd_deflater *deflater); 312 313 /* 314 * Deflates the |nva|, which has the |nvlen| name/value pairs, into 315 * the |bufs|. 316 * 317 * This function expands |bufs| as necessary to store the result. If 318 * buffers is full and the process still requires more space, this 319 * function fails and returns NGHTTP2_ERR_HEADER_COMP. 320 * 321 * After this function returns, it is safe to delete the |nva|. 322 * 323 * This function returns 0 if it succeeds, or one of the following 324 * negative error codes: 325 * 326 * NGHTTP2_ERR_NOMEM 327 * Out of memory. 328 * NGHTTP2_ERR_HEADER_COMP 329 * Deflation process has failed. 330 * NGHTTP2_ERR_BUFFER_ERROR 331 * Out of buffer space. 332 */ 333 int nghttp2_hd_deflate_hd_bufs(nghttp2_hd_deflater *deflater, 334 nghttp2_bufs *bufs, const nghttp2_nv *nva, 335 size_t nvlen); 336 337 /* 338 * Initializes |inflater| for inflating name/values pairs. 339 * 340 * This function returns 0 if it succeeds, or one of the following 341 * negative error codes: 342 * 343 * :enum:`NGHTTP2_ERR_NOMEM` 344 * Out of memory. 345 */ 346 int nghttp2_hd_inflate_init(nghttp2_hd_inflater *inflater, nghttp2_mem *mem); 347 348 /* 349 * Deallocates any resources allocated for |inflater|. 350 */ 351 void nghttp2_hd_inflate_free(nghttp2_hd_inflater *inflater); 352 353 /* 354 * Similar to nghttp2_hd_inflate_hd(), but this takes nghttp2_hd_nv 355 * instead of nghttp2_nv as output parameter |nv_out|. Other than 356 * that return values and semantics are the same as 357 * nghttp2_hd_inflate_hd(). 358 */ 359 ssize_t nghttp2_hd_inflate_hd_nv(nghttp2_hd_inflater *inflater, 360 nghttp2_hd_nv *nv_out, int *inflate_flags, 361 const uint8_t *in, size_t inlen, int in_final); 362 363 /* For unittesting purpose */ 364 int nghttp2_hd_emit_indname_block(nghttp2_bufs *bufs, size_t index, 365 nghttp2_nv *nv, int indexing_mode); 366 367 /* For unittesting purpose */ 368 int nghttp2_hd_emit_newname_block(nghttp2_bufs *bufs, nghttp2_nv *nv, 369 int indexing_mode); 370 371 /* For unittesting purpose */ 372 int nghttp2_hd_emit_table_size(nghttp2_bufs *bufs, size_t table_size); 373 374 /* For unittesting purpose */ 375 nghttp2_hd_nv nghttp2_hd_table_get(nghttp2_hd_context *context, size_t index); 376 377 /* For unittesting purpose */ 378 ssize_t nghttp2_hd_decode_length(uint32_t *res, size_t *shift_ptr, int *fin, 379 uint32_t initial, size_t shift, uint8_t *in, 380 uint8_t *last, size_t prefix); 381 382 /* Huffman encoding/decoding functions */ 383 384 /* 385 * Counts the required bytes to encode |src| with length |len|. 386 * 387 * This function returns the number of required bytes to encode given 388 * data, including padding of prefix of terminal symbol code. This 389 * function always succeeds. 390 */ 391 size_t nghttp2_hd_huff_encode_count(const uint8_t *src, size_t len); 392 393 /* 394 * Encodes the given data |src| with length |srclen| to the |bufs|. 395 * This function expands extra buffers in |bufs| if necessary. 396 * 397 * This function returns 0 if it succeeds, or one of the following 398 * negative error codes: 399 * 400 * NGHTTP2_ERR_NOMEM 401 * Out of memory. 402 * NGHTTP2_ERR_BUFFER_ERROR 403 * Out of buffer space. 404 */ 405 int nghttp2_hd_huff_encode(nghttp2_bufs *bufs, const uint8_t *src, 406 size_t srclen); 407 408 void nghttp2_hd_huff_decode_context_init(nghttp2_hd_huff_decode_context *ctx); 409 410 /* 411 * Decodes the given data |src| with length |srclen|. The |ctx| must 412 * be initialized by nghttp2_hd_huff_decode_context_init(). The result 413 * will be written to |buf|. This function assumes that |buf| has the 414 * enough room to store the decoded byte string. 415 * 416 * The caller must set the |fin| to nonzero if the given input is the 417 * final block. 418 * 419 * This function returns the number of read bytes from the |in|. 420 * 421 * If this function fails, it returns one of the following negative 422 * return codes: 423 * 424 * NGHTTP2_ERR_NOMEM 425 * Out of memory. 426 * NGHTTP2_ERR_HEADER_COMP 427 * Decoding process has failed. 428 */ 429 ssize_t nghttp2_hd_huff_decode(nghttp2_hd_huff_decode_context *ctx, 430 nghttp2_buf *buf, const uint8_t *src, 431 size_t srclen, int fin); 432 433 /* 434 * nghttp2_hd_huff_decode_failure_state returns nonzero if |ctx| 435 * indicates that huffman decoding context is in failure state. 436 */ 437 int nghttp2_hd_huff_decode_failure_state(nghttp2_hd_huff_decode_context *ctx); 438 439 #endif /* NGHTTP2_HD_H */ 440