lib/nghttp2_hd.h

   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
  38 #define NGHTTP2_HD_DEFAULT_MAX_BUFFER_SIZE NGHTTP2_DEFAULT_HEADER_TABLE_SIZE
  39 #define NGHTTP2_HD_ENTRY_OVERHEAD 32
  40
  41 /* The maximum length of one name/value pair.  This is the sum of the
  42    length of name and value.  This is not specified by the spec. We
  43    just chose the arbitrary size */
  44 #define NGHTTP2_HD_MAX_NV 65536
  45
  46 /* Default size of maximum table buffer size for encoder. Even if
  47    remote decoder notifies larger buffer size for its decoding,
  48    encoder only uses the memory up to this value. */
  49 #define NGHTTP2_HD_DEFAULT_MAX_DEFLATE_BUFFER_SIZE (1 << 12)
  50
  51 /* Exported for unit test */
  52 #define NGHTTP2_STATIC_TABLE_LENGTH 61
  53
  54 /* Generated by genlibtokenlookup.py */
  55 typedef enum {
  56   NGHTTP2_TOKEN__AUTHORITY = 0,
  57   NGHTTP2_TOKEN__METHOD = 1,
  58   NGHTTP2_TOKEN__PATH = 3,
  59   NGHTTP2_TOKEN__SCHEME = 5,
  60   NGHTTP2_TOKEN__STATUS = 7,
  61   NGHTTP2_TOKEN_ACCEPT_CHARSET = 14,
  62   NGHTTP2_TOKEN_ACCEPT_ENCODING = 15,
  63   NGHTTP2_TOKEN_ACCEPT_LANGUAGE = 16,
  64   NGHTTP2_TOKEN_ACCEPT_RANGES = 17,
  65   NGHTTP2_TOKEN_ACCEPT = 18,
  66   NGHTTP2_TOKEN_ACCESS_CONTROL_ALLOW_ORIGIN = 19,
  67   NGHTTP2_TOKEN_AGE = 20,
  68   NGHTTP2_TOKEN_ALLOW = 21,
  69   NGHTTP2_TOKEN_AUTHORIZATION = 22,
  70   NGHTTP2_TOKEN_CACHE_CONTROL = 23,
  71   NGHTTP2_TOKEN_CONTENT_DISPOSITION = 24,
  72   NGHTTP2_TOKEN_CONTENT_ENCODING = 25,
  73   NGHTTP2_TOKEN_CONTENT_LANGUAGE = 26,
  74   NGHTTP2_TOKEN_CONTENT_LENGTH = 27,
  75   NGHTTP2_TOKEN_CONTENT_LOCATION = 28,
  76   NGHTTP2_TOKEN_CONTENT_RANGE = 29,
  77   NGHTTP2_TOKEN_CONTENT_TYPE = 30,
  78   NGHTTP2_TOKEN_COOKIE = 31,
  79   NGHTTP2_TOKEN_DATE = 32,
  80   NGHTTP2_TOKEN_ETAG = 33,
  81   NGHTTP2_TOKEN_EXPECT = 34,
  82   NGHTTP2_TOKEN_EXPIRES = 35,
  83   NGHTTP2_TOKEN_FROM = 36,
  84   NGHTTP2_TOKEN_HOST = 37,
  85   NGHTTP2_TOKEN_IF_MATCH = 38,
  86   NGHTTP2_TOKEN_IF_MODIFIED_SINCE = 39,
  87   NGHTTP2_TOKEN_IF_NONE_MATCH = 40,
  88   NGHTTP2_TOKEN_IF_RANGE = 41,
  89   NGHTTP2_TOKEN_IF_UNMODIFIED_SINCE = 42,
  90   NGHTTP2_TOKEN_LAST_MODIFIED = 43,
  91   NGHTTP2_TOKEN_LINK = 44,
  92   NGHTTP2_TOKEN_LOCATION = 45,
  93   NGHTTP2_TOKEN_MAX_FORWARDS = 46,
  94   NGHTTP2_TOKEN_PROXY_AUTHENTICATE = 47,
  95   NGHTTP2_TOKEN_PROXY_AUTHORIZATION = 48,
  96   NGHTTP2_TOKEN_RANGE = 49,
  97   NGHTTP2_TOKEN_REFERER = 50,
  98   NGHTTP2_TOKEN_REFRESH = 51,
  99   NGHTTP2_TOKEN_RETRY_AFTER = 52,
 100   NGHTTP2_TOKEN_SERVER = 53,
 101   NGHTTP2_TOKEN_SET_COOKIE = 54,
 102   NGHTTP2_TOKEN_STRICT_TRANSPORT_SECURITY = 55,
 103   NGHTTP2_TOKEN_TRANSFER_ENCODING = 56,
 104   NGHTTP2_TOKEN_USER_AGENT = 57,
 105   NGHTTP2_TOKEN_VARY = 58,
 106   NGHTTP2_TOKEN_VIA = 59,
 107   NGHTTP2_TOKEN_WWW_AUTHENTICATE = 60,
 108   NGHTTP2_TOKEN_TE,
 109   NGHTTP2_TOKEN_CONNECTION,
 110   NGHTTP2_TOKEN_KEEP_ALIVE,
 111   NGHTTP2_TOKEN_PROXY_CONNECTION,
 112   NGHTTP2_TOKEN_UPGRADE
 113 } nghttp2_token;
 114
 115 typedef enum {
 116   NGHTTP2_HD_FLAG_NONE = 0,
 117   /* Indicates name was dynamically allocated and must be freed */
 118   NGHTTP2_HD_FLAG_NAME_ALLOC = 1,
 119   /* Indicates value was dynamically allocated and must be freed */
 120   NGHTTP2_HD_FLAG_VALUE_ALLOC = 1 << 1,
 121   /* Indicates that the name was gifted to the entry and no copying
 122      necessary. */
 123   NGHTTP2_HD_FLAG_NAME_GIFT = 1 << 2,
 124   /* Indicates that the value was gifted to the entry and no copying
 125      necessary. */
 126   NGHTTP2_HD_FLAG_VALUE_GIFT = 1 << 3
 127 } nghttp2_hd_flags;
 128
 129 typedef struct {
 130   nghttp2_nv nv;
 131   /* nghttp2_token value for nv.name.  It could be -1 if we have no
 132      token for that header field name. */
 133   int token;
 134   /* Reference count */
 135   uint8_t ref;
 136   uint8_t flags;
 137 } nghttp2_hd_entry;
 138
 139 typedef struct {
 140   nghttp2_hd_entry **buffer;
 141   size_t mask;
 142   size_t first;
 143   size_t len;
 144 } nghttp2_hd_ringbuf;
 145
 146 typedef enum {
 147   NGHTTP2_HD_OPCODE_NONE,
 148   NGHTTP2_HD_OPCODE_INDEXED,
 149   NGHTTP2_HD_OPCODE_NEWNAME,
 150   NGHTTP2_HD_OPCODE_INDNAME
 151 } nghttp2_hd_opcode;
 152
 153 typedef enum {
 154   NGHTTP2_HD_STATE_OPCODE,
 155   NGHTTP2_HD_STATE_READ_TABLE_SIZE,
 156   NGHTTP2_HD_STATE_READ_INDEX,
 157   NGHTTP2_HD_STATE_NEWNAME_CHECK_NAMELEN,
 158   NGHTTP2_HD_STATE_NEWNAME_READ_NAMELEN,
 159   NGHTTP2_HD_STATE_NEWNAME_READ_NAMEHUFF,
 160   NGHTTP2_HD_STATE_NEWNAME_READ_NAME,
 161   NGHTTP2_HD_STATE_CHECK_VALUELEN,
 162   NGHTTP2_HD_STATE_READ_VALUELEN,
 163   NGHTTP2_HD_STATE_READ_VALUEHUFF,
 164   NGHTTP2_HD_STATE_READ_VALUE
 165 } nghttp2_hd_inflate_state;
 166
 167 typedef enum {
 168   NGHTTP2_HD_WITH_INDEXING,
 169   NGHTTP2_HD_WITHOUT_INDEXING,
 170   NGHTTP2_HD_NEVER_INDEXING
 171 } nghttp2_hd_indexing_mode;
 172
 173 typedef struct {
 174   /* dynamic header table */
 175   nghttp2_hd_ringbuf hd_table;
 176   /* Memory allocator */
 177   nghttp2_mem *mem;
 178   /* Abstract buffer size of hd_table as described in the spec. This
 179      is the sum of length of name/value in hd_table +
 180      NGHTTP2_HD_ENTRY_OVERHEAD bytes overhead per each entry. */
 181   size_t hd_table_bufsize;
 182   /* The effective header table size. */
 183   size_t hd_table_bufsize_max;
 184   /* If inflate/deflate error occurred, this value is set to 1 and
 185      further invocation of inflate/deflate will fail with
 186      NGHTTP2_ERR_HEADER_COMP. */
 187   uint8_t bad;
 188 } nghttp2_hd_context;
 189
 190 struct nghttp2_hd_deflater {
 191   nghttp2_hd_context ctx;
 192   /* The upper limit of the header table size the deflater accepts. */
 193   size_t deflate_hd_table_bufsize_max;
 194   /* Minimum header table size notified in the next context update */
 195   size_t min_hd_table_bufsize_max;
 196   /* If nonzero, send header table size using encoding context update
 197      in the next deflate process */
 198   uint8_t notify_table_size_change;
 199 };
 200
 201 struct nghttp2_hd_inflater {
 202   nghttp2_hd_context ctx;
 203   /* header buffer */
 204   nghttp2_bufs nvbufs;
 205   /* Stores current state of huffman decoding */
 206   nghttp2_hd_huff_decode_context huff_decode_ctx;
 207   /* Pointer to the nghttp2_hd_entry which is used current header
 208      emission. This is required because in some cases the
 209      ent_keep->ref == 0 and we have to keep track of it. */
 210   nghttp2_hd_entry *ent_keep;
 211   /* Pointer to the name/value pair buffer which is used in the
 212      current header emission. */
 213   uint8_t *nv_keep;
 214   /* The number of bytes to read */
 215   size_t left;
 216   /* The index in indexed repr or indexed name */
 217   size_t index;
 218   /* The length of new name encoded in literal.  For huffman encoded
 219      string, this is the length after it is decoded. */
 220   size_t newnamelen;
 221   /* The maximum header table size the inflater supports. This is the
 222      same value transmitted in SETTINGS_HEADER_TABLE_SIZE */
 223   size_t settings_hd_table_bufsize_max;
 224   /* The number of next shift to decode integer */
 225   size_t shift;
 226   nghttp2_hd_opcode opcode;
 227   nghttp2_hd_inflate_state state;
 228   /* nonzero if string is huffman encoded */
 229   uint8_t huffman_encoded;
 230   /* nonzero if deflater requires that current entry is indexed */
 231   uint8_t index_required;
 232   /* nonzero if deflater requires that current entry must not be
 233      indexed */
 234   uint8_t no_index;
 235 };
 236
 237 /*
 238  * Initializes the |ent| members. If NGHTTP2_HD_FLAG_NAME_ALLOC bit
 239  * set in the |flags|, the content pointed by the |name| with length
 240  * |namelen| is copied. Likewise, if NGHTTP2_HD_FLAG_VALUE_ALLOC bit
 241  * set in the |flags|, the content pointed by the |value| with length
 242  * |valuelen| is copied.  The |token| is enum number looked up by
 243  * |name|.  It could be -1 if we don't have that enum value.
 244  *
 245  * This function returns 0 if it succeeds, or one of the following
 246  * negative error codes:
 247  *
 248  * NGHTTP2_ERR_NOMEM
 249  *     Out of memory.
 250  */
 251 int nghttp2_hd_entry_init(nghttp2_hd_entry *ent, uint8_t flags, uint8_t *name,
 252                           size_t namelen, uint8_t *value, size_t valuelen,
 253                           int token, nghttp2_mem *mem);
 254
 255 void nghttp2_hd_entry_free(nghttp2_hd_entry *ent, nghttp2_mem *mem);
 256
 257 /*
 258  * Initializes |deflater| for deflating name/values pairs.
 259  *
 260  * The encoder only uses up to
 261  * NGHTTP2_HD_DEFAULT_MAX_DEFLATE_BUFFER_SIZE bytes for header table
 262  * even if the larger value is specified later in
 263  * nghttp2_hd_change_table_size().
 264  *
 265  * This function returns 0 if it succeeds, or one of the following
 266  * negative error codes:
 267  *
 268  * NGHTTP2_ERR_NOMEM
 269  *     Out of memory.
 270  */
 271 int nghttp2_hd_deflate_init(nghttp2_hd_deflater *deflater, nghttp2_mem *mem);
 272
 273 /*
 274  * Initializes |deflater| for deflating name/values pairs.
 275  *
 276  * The encoder only uses up to |deflate_hd_table_bufsize_max| bytes
 277  * for header table even if the larger value is specified later in
 278  * nghttp2_hd_change_table_size().
 279  *
 280  * This function returns 0 if it succeeds, or one of the following
 281  * negative error codes:
 282  *
 283  * NGHTTP2_ERR_NOMEM
 284  *     Out of memory.
 285  */
 286 int nghttp2_hd_deflate_init2(nghttp2_hd_deflater *deflater,
 287                              size_t deflate_hd_table_bufsize_max,
 288                              nghttp2_mem *mem);
 289
 290 /*
 291  * Deallocates any resources allocated for |deflater|.
 292  */
 293 void nghttp2_hd_deflate_free(nghttp2_hd_deflater *deflater);
 294
 295 /*
 296  * Deflates the |nva|, which has the |nvlen| name/value pairs, into
 297  * the |bufs|.
 298  *
 299  * This function expands |bufs| as necessary to store the result. If
 300  * buffers is full and the process still requires more space, this
 301  * funtion fails and returns NGHTTP2_ERR_HEADER_COMP.
 302  *
 303  * After this function returns, it is safe to delete the |nva|.
 304  *
 305  * This function returns 0 if it succeeds, or one of the following
 306  * negative error codes:
 307  *
 308  * NGHTTP2_ERR_NOMEM
 309  *     Out of memory.
 310  * NGHTTP2_ERR_HEADER_COMP
 311  *     Deflation process has failed.
 312  * NGHTTP2_ERR_BUFFER_ERROR
 313  *     Out of buffer space.
 314  */
 315 int nghttp2_hd_deflate_hd_bufs(nghttp2_hd_deflater *deflater,
 316                                nghttp2_bufs *bufs, const nghttp2_nv *nva,
 317                                size_t nvlen);
 318
 319 /*
 320  * Initializes |inflater| for inflating name/values pairs.
 321  *
 322  * This function returns 0 if it succeeds, or one of the following
 323  * negative error codes:
 324  *
 325  * :enum:`NGHTTP2_ERR_NOMEM`
 326  *     Out of memory.
 327  */
 328 int nghttp2_hd_inflate_init(nghttp2_hd_inflater *inflater, nghttp2_mem *mem);
 329
 330 /*
 331  * Deallocates any resources allocated for |inflater|.
 332  */
 333 void nghttp2_hd_inflate_free(nghttp2_hd_inflater *inflater);
 334
 335 /*
 336  * Similar to nghttp2_hd_inflate_hd(), but this takes additional
 337  * output parameter |token|.  On successful header emission, it
 338  * contains nghttp2_token value for nv_out->name.  It could be -1 if
 339  * we don't have enum value for the name.  Other than that return
 340  * values and semantics are the same as nghttp2_hd_inflate_hd().
 341  */
 342 ssize_t nghttp2_hd_inflate_hd2(nghttp2_hd_inflater *inflater,
 343                                nghttp2_nv *nv_out, int *inflate_flags,
 344                                int *token, uint8_t *in, size_t inlen,
 345                                int in_final);
 346
 347 /* For unittesting purpose */
 348 int nghttp2_hd_emit_indname_block(nghttp2_bufs *bufs, size_t index,
 349                                   nghttp2_nv *nv, int indexing_mode);
 350
 351 /* For unittesting purpose */
 352 int nghttp2_hd_emit_newname_block(nghttp2_bufs *bufs, nghttp2_nv *nv,
 353                                   int indexing_mode);
 354
 355 /* For unittesting purpose */
 356 int nghttp2_hd_emit_table_size(nghttp2_bufs *bufs, size_t table_size);
 357
 358 /* For unittesting purpose */
 359 nghttp2_hd_entry *nghttp2_hd_table_get(nghttp2_hd_context *context,
 360                                        size_t index);
 361
 362 /* For unittesting purpose */
 363 ssize_t nghttp2_hd_decode_length(uint32_t *res, size_t *shift_ptr, int *final,
 364                                  uint32_t initial, size_t shift, uint8_t *in,
 365                                  uint8_t *last, size_t prefix);
 366
 367 /* Huffman encoding/decoding functions */
 368
 369 /*
 370  * Counts the required bytes to encode |src| with length |len|.
 371  *
 372  * This function returns the number of required bytes to encode given
 373  * data, including padding of prefix of terminal symbol code. This
 374  * function always succeeds.
 375  */
 376 size_t nghttp2_hd_huff_encode_count(const uint8_t *src, size_t len);
 377
 378 /*
 379  * Encodes the given data |src| with length |srclen| to the |bufs|.
 380  * This function expands extra buffers in |bufs| if necessary.
 381  *
 382  * This function returns 0 if it succeeds, or one of the following
 383  * negative error codes:
 384  *
 385  * NGHTTP2_ERR_NOMEM
 386  *     Out of memory.
 387  * NGHTTP2_ERR_BUFFER_ERROR
 388  *     Out of buffer space.
 389  */
 390 int nghttp2_hd_huff_encode(nghttp2_bufs *bufs, const uint8_t *src,
 391                            size_t srclen);
 392
 393 void nghttp2_hd_huff_decode_context_init(nghttp2_hd_huff_decode_context *ctx);
 394
 395 /*
 396  * Decodes the given data |src| with length |srclen|. The |ctx| must
 397  * be initialized by nghttp2_hd_huff_decode_context_init(). The result
 398  * will be added to |dest|. This function may expand |dest| as
 399  * needed. The caller is responsible to release the memory of |dest|
 400  * by calling nghttp2_bufs_free().
 401  *
 402  * The caller must set the |final| to nonzero if the given input is
 403  * the final block.
 404  *
 405  * This function returns the number of read bytes from the |in|.
 406  *
 407  * If this function fails, it returns one of the following negative
 408  * return codes:
 409  *
 410  * NGHTTP2_ERR_NOMEM
 411  *     Out of memory.
 412  * NGHTTP2_ERR_BUFFER_ERROR
 413  *     Maximum buffer capacity size exceeded.
 414  * NGHTTP2_ERR_HEADER_COMP
 415  *     Decoding process has failed.
 416  */
 417 ssize_t nghttp2_hd_huff_decode(nghttp2_hd_huff_decode_context *ctx,
 418                                nghttp2_bufs *bufs, const uint8_t *src,
 419                                size_t srclen, int final);
 420
 421 #endif /* NGHTTP2_HD_H */