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