"Fossies" - the Fresh Open Source Software Archive

Member "haproxy-2.0.0/include/common/hpack-tbl.h" (16 Jun 2019, 10118 Bytes) of package /linux/misc/haproxy-2.0.0.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "hpack-tbl.h" see the Fossies "Dox" file reference documentation and the last Fossies "Diffs" side-by-side code changes report: 1.9.6_vs_1.9.7.

    1 /*
    2  * HPACK header table management (RFC7541) - type definitions and prototypes
    3  *
    4  * Copyright (C) 2014-2017 Willy Tarreau <willy@haproxy.org>
    5  * Copyright (C) 2017 HAProxy Technologies
    6  *
    7  * Permission is hereby granted, free of charge, to any person obtaining
    8  * a copy of this software and associated documentation files (the
    9  * "Software"), to deal in the Software without restriction, including
   10  * without limitation the rights to use, copy, modify, merge, publish,
   11  * distribute, sublicense, and/or sell copies of the Software, and to
   12  * permit persons to whom the Software is furnished to do so, subject to
   13  * the following conditions:
   14  *
   15  * The above copyright notice and this permission notice shall be
   16  * included in all copies or substantial portions of the Software.
   17  *
   18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
   19  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
   20  * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
   21  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
   22  * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
   23  * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
   24  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
   25  * OTHER DEALINGS IN THE SOFTWARE.
   26  */
   27 #ifndef _COMMON_HPACK_TBL_H
   28 #define _COMMON_HPACK_TBL_H
   29 
   30 #include <inttypes.h>
   31 #include <stdlib.h>
   32 #include <common/config.h>
   33 #include <common/http-hdr.h>
   34 #include <common/ist.h>
   35 
   36 /* Dynamic Headers Table, usable for tables up to 4GB long and values of 64kB-1.
   37  * The model can be improved by using offsets relative to the table entry's end
   38  * or to the end of the area, or by moving the descriptors at the end of the
   39  * table and the data at the beginning. This entry is 8 bytes long, which is 1/4
   40  * of the bookkeeping planned by the HPACK spec. Thus it saves 24 bytes per
   41  * header field, meaning that even with a single header, 24 extra bytes can be
   42  * stored (ie one such descriptor). At 29.2 average bytes per header field as
   43  * found in the hpack test case, that's slightly more than 1.5kB of space saved
   44  * from a 4kB block, resulting in contiguous space almost always being
   45  * available.
   46  *
   47  * Principle: the table is stored in a contiguous array containing both the
   48  * descriptors and the contents. Descriptors are stored at the beginning of the
   49  * array while contents are stored starting from the end. Most of the time there
   50  * is enough room left in the table to insert a new header field, thanks to the
   51  * savings on the descriptor size. Thus by inserting headers from the end it's
   52  * possible to maximize the delay before a collision of DTEs and data. In order
   53  * to always insert from the right, we need to keep a reference to the latest
   54  * inserted element and look before it. The last inserted cell's address defines
   55  * the lowest konwn address still in use, unless the area wraps in which case
   56  * the available space lies between the end of the tail and the beginning of the
   57  * head.
   58  *
   59  * In order to detect collisions between data blocks and DTEs, we also maintain
   60  * an index to the lowest element facing the DTE table, called "front". This one
   61  * is updated each time an element is inserted before it. Once the buffer wraps,
   62  * this element doesn't have to be updated anymore until it is released, in
   63  * which case the buffer doesn't wrap anymore and the front element becomes the
   64  * head again.
   65  *
   66  * Various heuristics are possible concerning the opportunity to wrap the
   67  * entries to limit the risk of collisions with the DTE, but experimentation
   68  * shows that thanks to the important savings made on the descriptors, the
   69  * likeliness of finding a large amount of free space at the end of the area is
   70  * much higher than the risk of colliding, so in the end the most naive
   71  * algorithms work pretty fine. Typical ratios of 1 collision per 2000 requests
   72  * have been observed.
   73  *
   74  * The defragmentation should be rare ; a study on live data shows on average
   75  * 29.2 bytes used per header field. This plus the 32 bytes overhead fix an
   76  * average of 66.9 header fields per 4kB table. This brings a 1606 bytes saving
   77  * using the current storage description, ensuring that oldest headers are
   78  * linearly removed by the sender before fragmentation occurs. This means that
   79  * for all smaller header fields there will not be any requirement to defragment
   80  * the area and most of the time it will even be possible to copy the old values
   81  * directly within the buffer after creating a new entry. On average within the
   82  * available space there will be enough room to store 1606/(29.2+8)=43 extra
   83  * header fields without switching to another place.
   84  *
   85  * The table header fits in the table itself, it only takes 16 bytes, so in the
   86  * worst case (1 single header) it's possible to store 4096 - 16 - 8 = 4072
   87  * data bytes, which is larger than the 4064 the protocol requires (4096 - 32).
   88  */
   89 
   90 /* One dynamic table entry descriptor */
   91 struct hpack_dte {
   92     uint32_t addr;  /* storage address, relative to the dte address */
   93     uint16_t nlen;  /* header name length */
   94     uint16_t vlen;  /* header value length */
   95 };
   96 
   97 /* Note: the table's head plus a struct hpack_dte must be smaller than or equal to 32
   98  * bytes so that a single large header can always fit. Here that's 16 bytes for
   99  * the header, plus 8 bytes per slot.
  100  * Note that when <used> == 0, front, head, and wrap are undefined.
  101  */
  102 struct hpack_dht {
  103     uint32_t size;  /* allocated table size in bytes */
  104     uint32_t total; /* sum of nlen + vlen in bytes */
  105     uint16_t front; /* slot number of the first node after the idx table */
  106     uint16_t wrap;  /* number of allocated slots, wraps here */
  107     uint16_t head;  /* last inserted slot number */
  108     uint16_t used;  /* number of slots in use */
  109     struct hpack_dte dte[0]; /* dynamic table entries */
  110 };
  111 
  112 /* supported hpack encoding/decoding errors */
  113 enum {
  114     HPACK_ERR_NONE = 0,           /* no error */
  115     HPACK_ERR_ALLOC_FAIL,         /* memory allocation error */
  116     HPACK_ERR_UNKNOWN_OPCODE,     /* invalid first byte */
  117     HPACK_ERR_TRUNCATED,          /* truncated stream */
  118     HPACK_ERR_HUFFMAN,            /* huffman decoding error */
  119     HPACK_ERR_INVALID_PHDR,       /* invalid pseudo header field name */
  120     HPACK_ERR_MISPLACED_PHDR,     /* pseudo header field after a regular header field */
  121     HPACK_ERR_DUPLICATE_PHDR,     /* duplicate pseudo header field */
  122     HPACK_ERR_DHT_INSERT_FAIL,    /* failed to insert into DHT */
  123     HPACK_ERR_TOO_LARGE,          /* decoded request/response is too large */
  124     HPACK_ERR_MISSING_METHOD,     /* :method is missing */
  125     HPACK_ERR_MISSING_SCHEME,     /* :scheme is missing */
  126     HPACK_ERR_MISSING_PATH,       /* :path is missing */
  127     HPACK_ERR_MISSING_AUTHORITY,  /* :authority is missing with CONNECT */
  128     HPACK_ERR_SCHEME_NOT_ALLOWED, /* :scheme not allowed with CONNECT */
  129     HPACK_ERR_PATH_NOT_ALLOWED,   /* :path not allowed with CONNECT */
  130     HPACK_ERR_INVALID_ARGUMENT,   /* an invalid argument was passed */
  131 };
  132 
  133 /* static header table as in RFC7541 Appendix A. [0] unused. */
  134 #define HPACK_SHT_SIZE 62
  135 extern const struct http_hdr hpack_sht[HPACK_SHT_SIZE];
  136 
  137 extern int __hpack_dht_make_room(struct hpack_dht *dht, unsigned int needed);
  138 extern int hpack_dht_insert(struct hpack_dht *dht, struct ist name, struct ist value);
  139 
  140 /* return a pointer to the entry designated by index <idx> (starting at 1) or
  141  * NULL if this index is not there.
  142  */
  143 static inline const struct hpack_dte *hpack_get_dte(const struct hpack_dht *dht, uint16_t idx)
  144 {
  145     idx--;
  146 
  147     if (idx >= dht->used)
  148         return NULL;
  149 
  150     if (idx <= dht->head)
  151         idx = dht->head - idx;
  152     else
  153         idx = dht->head - idx + dht->wrap;
  154 
  155     return &dht->dte[idx];
  156 }
  157 
  158 /* returns non-zero if <idx> is valid for table <dht> */
  159 static inline int hpack_valid_idx(const struct hpack_dht *dht, uint32_t idx)
  160 {
  161     return idx < dht->used + HPACK_SHT_SIZE;
  162 }
  163 
  164 /* return a pointer to the header name for entry <dte>. */
  165 static inline struct ist hpack_get_name(const struct hpack_dht *dht, const struct hpack_dte *dte)
  166 {
  167     struct ist ret = {
  168         .ptr = (void *)dht + dte->addr,
  169         .len = dte->nlen,
  170     };
  171     return ret;
  172 }
  173 
  174 /* return a pointer to the header value for entry <dte>. */
  175 static inline struct ist hpack_get_value(const struct hpack_dht *dht, const struct hpack_dte *dte)
  176 {
  177     struct ist ret = {
  178         .ptr = (void *)dht + dte->addr + dte->nlen,
  179         .len = dte->vlen,
  180     };
  181     return ret;
  182 }
  183 
  184 /* takes an idx, returns the associated name */
  185 static inline struct ist hpack_idx_to_name(const struct hpack_dht *dht, uint32_t idx)
  186 {
  187     const struct hpack_dte *dte;
  188 
  189     if (idx < HPACK_SHT_SIZE)
  190         return hpack_sht[idx].n;
  191 
  192     dte = hpack_get_dte(dht, idx - HPACK_SHT_SIZE + 1);
  193     if (!dte)
  194         return ist("### ERR ###"); // error
  195 
  196     return hpack_get_name(dht, dte);
  197 }
  198 
  199 /* takes an idx, returns the associated value */
  200 static inline struct ist hpack_idx_to_value(const struct hpack_dht *dht, uint32_t idx)
  201 {
  202     const struct hpack_dte *dte;
  203 
  204     if (idx < HPACK_SHT_SIZE)
  205         return hpack_sht[idx].v;
  206 
  207     dte = hpack_get_dte(dht, idx - HPACK_SHT_SIZE + 1);
  208     if (!dte)
  209         return ist("### ERR ###"); // error
  210 
  211     return hpack_get_value(dht, dte);
  212 }
  213 
  214 /* Purges table dht until a header field of <needed> bytes fits according to
  215  * the protocol (adding 32 bytes overhead). Returns non-zero on success, zero
  216  * on failure (ie: table empty but still not sufficient).
  217  */
  218 static inline int hpack_dht_make_room(struct hpack_dht *dht, unsigned int needed)
  219 {
  220     if (dht->used * 32 + dht->total + needed + 32 <= dht->size)
  221         return 1;
  222     else if (!dht->used)
  223         return 0;
  224 
  225     return __hpack_dht_make_room(dht, needed);
  226 }
  227 
  228 /* allocate a dynamic headers table of <size> bytes and return it initialized */
  229 static inline void hpack_dht_init(struct hpack_dht *dht, uint32_t size)
  230 {
  231     dht->size = size;
  232     dht->total = 0;
  233     dht->used = 0;
  234 }
  235 
  236 /* allocate a dynamic headers table of <size> bytes and return it initialized */
  237 static inline struct hpack_dht *hpack_dht_alloc(uint32_t size)
  238 {
  239     struct hpack_dht *dht;
  240 
  241     dht = malloc(size);
  242     if (!dht)
  243         return dht;
  244 
  245     hpack_dht_init(dht, size);
  246     return dht;
  247 }
  248 
  249 /* free a dynamic headers table */
  250 static inline void hpack_dht_free(struct hpack_dht *dht)
  251 {
  252     free(dht);
  253 }
  254 
  255 #endif /* _COMMON_HPACK_TBL_H */