Adding upstream version 2.9.5.upstream/2.9.5

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 570 insertions, 0 deletions

diff --git a/doc/internals/api/htx-api.txt b/doc/internals/api/htx-api.txt
new file mode 100644
index 0000000..62b3093
--- /dev/null
+++ b/doc/internals/api/htx-api.txt
@@ -0,0 +1,570 @@
+                -----------------------------------------------
+                                   HTX API
+                                  Version 1.1
+                          ( Last update: 2021-02-24 )
+                -----------------------------------------------
+                          Author : Christopher Faulet
+                      Contact : cfaulet at haproxy dot com
+
+1. Background
+
+Historically, HAProxy stored HTTP messages in a raw fashion in buffers, keeping
+parsing information separately in a "struct http_msg" owned by the stream. It was
+optimized to the data transfer, but not so much for rewrites. It was also HTTP/1
+centered. While it was the only HTTP version supported, it was not a
+problem. But with the rise of HTTP/2, it starts to be hard to still use this
+representation.
+
+At the first age of the HTTP/2 in HAProxy, H2 messages were converted into
+H1. This was terribly unefficient because it required two parsing passes, a
+first one in H2 and a second one in H1, with a conversion in the middle. And of
+course, the same was also true in the opposite direction. outgoing H1 messages
+had to be converted back in H2 to be sent. Even worse, because the H2->H1
+conversion, only client H2 connections were supported.
+
+So, to address all these problems, we decided to replace the old raw
+representation by a version-agnostic and self-structured internal HTTP
+representation, the HTX. As an additional benefit, with this new representation,
+the message parsing and its processing are now separated, making all the HTTP
+analysis simpler and cleaner. The parsing of HTTP messages is now handled by
+the multiplexers (h1 or h2).
+
+
+2. The HTX message
+
+The HTX is a structure containing useful information about an HTTP message
+followed by a contiguous array with some parts of the message. These parts are
+called blocks. A block is composed of metadata (htx_blk) and an associated
+payload. Blocks' metadata are stored starting from the end of the array while
+their payload are stored at the beginning. Blocks' metadata are often simply
+called blocks. it is a misuse of language that's simplify explanations.
+
+Internally, this structure is "hidden" in a buffer. This way, there are few
+changes into intermediate layers (stream-interface and channels). They still
+manipulate buffers. Only the multiplexer and the stream have to know how data
+are really stored. From the HTX perspective, a buffer is just a memory
+area. When an HTX message is stored in a buffer, this one appears as full.
+
+  * General view of an HTX message :
+
+
+  buffer->area
+    |
+    |<------------ buffer->size == buffer->data ----------------------|
+    |                                                                 |
+    |     |<------------- Blocks array (htx->size) ------------------>|
+    V     |                                                           |
+    +-----+-----------------+-------------------------+---------------+
+    | HTX |   PAYLOADS ==>  |                         |  <== HTX_BLKs |
+    +-----+-----------------+-------------------------+---------------+
+          |                 |                         |               |
+          |<-payloads part->|<----- free space ------>|<-blocks part->|
+              (htx->data)
+
+
+The blocks part remains linear and sorted. It may be see as an array with
+negative indexes. But, instead of using negative indexes, we use positive
+positions to identify a block. This position is then converted to an address
+relatively to the beginning of the blocks array.
+
+                tail                                 head
+                 |                                     |
+                 V                                     V
+     .....--+----+-----------------------+------+------+
+            | Bn |       ...             |  B1  |  B0  |
+     .....--+----+-----------------------+------+------+
+                 ^                       ^      ^
+ Addr of the block       Addr of the block      Addr of the block
+ at the position N       at the position 1      at the position 0
+
+
+In the HTX structure, 3 "special" positions are stored :
+
+    - tail  : Position of the newest inserted block
+    - head  : Position of the oldest inserted block
+    - first : Position of the first block to (re)start the analyse
+
+The blocks part never wrap. If we have no space to allocate a new block and if
+there is a hole at the beginning of the blocks part (so at the end of the blocks
+array), we move back all blocks.
+
+
+      tail           head                                tail           head
+       |              |                                   |              |
+       V              V                                   V              V
+    ...+--------------+---------+    blocks  ...----------+--------------+
+       | X== HTX_BLKS |         |    defrag               | <== HTX_BLKS |
+    ...+--------------+---------+    =====>  ...----------+--------------+
+
+
+The payloads part is a raw space that may wrap. A block's payload must never be
+accessed directly. Instead a block must be selected to retrieve the address of
+its payload.
+
+
+          +------------------------( B0.addr )--------------------------+
+          |    +-------------------( B1.addr )----------------------+   |
+          |    |       +-----------( B2.addr )----------------+     |   |
+          V    V       V                                      |     |   |
+    +-----+----+-------+----+--------+-------------+-------+----+----+----+
+    | HTX | P0 |   P1  | P2 | ...==> |             | <=... | B2 | B1 | B0 |
+    +-----+----+-------+----+--------+-------------+-------+----+----+----+
+
+
+Because the payloads part may wrap, there are 2 usable free spaces :
+
+    - The free space in front of the blocks part. This one is used if and only if
+      the other one was not used yet.
+
+    - The free space at the beginning of the message. Once this one is used, the
+      other one is never used again, until a message defragmentation.
+
+
+  * Linear payloads part :
+
+
+      head_addr             end_addr     tail_addr
+          |                    |             |
+          V                    V             V
+    +-----+--------------------+-------------+--------------------+-------...
+    | HTX |                    |   PAYLOADS  |                    | HTX_BLKs
+    +-----+--------------------+-------------+--------------------+-------...
+          |<-- free space 2 -->|             |<-- free space 1 -->|
+     (used if the other is too small)          (used in priority)
+
+
+  * Wrapping payloads part :
+
+
+                            head_addr end_addr        tail_addr
+                                |        |                |
+                                V        V                V
+    +-----+----+----------------+--------+----------------+-------+-------...
+    | HTX |    | PAYLOADS part2 |        | PAYLOADS part1 |       | HTX_BLKs
+    +-----+----+----------------+--------+----------------+-------+-------...
+          |<-->|                |<------>|                |<----->|
+         unusable               free space                 unusable
+        free space                                        free space
+
+
+Finally, when the usable free space is not enough to store a new block, unusable
+parts may be get back with a full defragmentation. The payloads part is then
+realigned at the beginning of the blocks array and the free space becomes
+continuous again.
+
+
+3. The HTX blocks
+
+An HTX block can be as well a start-line as a header, a body part or a
+trailer. For all these types of block, a payload is attached to the block. It
+can also be a marker, the end-of-headers or end-of-trailers. For these blocks,
+there is no payload but it counts for a byte. It is important to not skip it
+when data are forwarded.
+
+As already said, a block is composed of metadata and a payload. Metadata are
+stored in the blocks part and are composed of 2 fields :
+
+    - info : It a 32 bits field containing the block's type on 4 bits followed
+             by the payload length. See below for details.
+
+    - addr : The payload's address, if any, relatively to the beginning the
+             array used to store part of the HTTP message itself.
+
+
+  * Block's info representation :
+
+    0b 0000 0000 0000 0000 0000 0000 0000 0000
+       ---- ------------------------ ---------
+       type     value (1 MB max)     name length (header/trailer - 256B max)
+            ----------------------------------
+                 data length (256 MB max)
+     (body, method, path, version, status, reason)
+
+
+Supported types are :
+
+    - 0000  (0) : The request start-line
+    - 0001  (1) : The response start-line
+    - 0010  (2) : A header block
+    - 0011  (3) : The end-of-headers marker
+    - 0100  (4) : A data block
+    - 0101  (5) : A trailer block
+    - 0110  (6) : The end-of-trailers marker
+    - 1111 (15) : An unused block
+
+Other types are unused for now and reserved for futur extensions.
+
+An HTX message is typically composed of following blocks, in this order :
+
+    - a start-line
+    - zero or more header blocks
+    - an end-of-headers marker
+    - zero or more data blocks
+    - zero or more trailer blocks (optional)
+    - an end-of-trailers marker (optional but always set if there is at least
+      one trailer block)
+
+Only one HTTP request at a time can be stored in an HTX message. For HTTP
+response, it is more complicated. Only one "final" response can be stored in an
+HTX message. It is a response with status-code 101 or greater or equal to
+200. But it may be preceded by several 1xx informational responses. Such
+responses are part of the same HTX message.
+
+When the end of the message is reached a special flag is set on the message
+(HTX_FL_EOM). It means no more data are expected for this message, except
+tunneled data. But tunneled data will never be mixed with message data to avoid
+ambiguities. Thus once the flag marking the end of the message is set, it is
+easy to know the message ends. The end is reached if the HTX message is empty or
+on the tail HTX block in the HTX message. Once all blocks of the HTX message are
+consumed, tunneled data, if any, may be transferred.
+
+
+3.1. The start-line
+
+Every HTX message starts with a start-line. Its payload is a "struct htx_sl". In
+addition to the parts of the HTTP start-line, this structure contains some
+information about the represented HTTP message, mainly in the form of flags
+(HTX_SL_F_*). For instance, if an HTTP message contains the header
+"conten-length", then the flag HTX_SL_F_CLEN is set.
+
+Each HTTP message has its own start-line. So an HTX request has one and only one
+start-line because it must contain only one HTTP request at a time. But an HTX
+response may have more than one start-line if the final HTTP response is
+precedeed by some 1xx informational responses.
+
+In HTTP/2, there is no start-line. So the H2 multiplexer must create one when it
+converts an H2 message to HTX :
+
+    - For the request, it uses the pseudo headers ":method", ":path" or
+      ":authority" depending on the method and the hardcoded version "HTTP/2.0".
+
+    - For the response, it used the hardcoded version "HTTP/2.0", the
+      pseudo-header ":status" and an empty reason.
+
+
+3.2. The headers and trailers
+
+HTX Headers and trailers are quite similar. Different types are used to simplify
+headers processing. But from the HTX point of view, there is no real difference,
+except their position in the HTX message. The header blocks always follow an HTX
+start-line while trailer blocks come after the data. If there is no data, they
+follow the end-of-headers marker.
+
+Headers and trailers are the only blocks containing a Key/Value payload. The
+corresponding end-of marker must always be placed after each group to mark, as
+it name suggests, the end.
+
+In HTTP/1, trailers are only present on chunked messages. But chunked messages
+do not always have trailers. In this case, the end-of-trailers block may or may
+not be present. Multiplexers must be able to handle both situations. In HTTP/2,
+trailers are only present if a HEADERS frame is sent after DATA frames.
+
+
+3.3. The data
+
+The payload body of an HTTP message is stored as DATA blocks in the HTX
+message. For HTTP/1 messages, it is the message body without the chunks
+formatting, if any. For HTTP/2, it is the payload of DATA frames.
+
+The DATA blocks are the only HTX blocks that may be partially processed (copied
+or removed). All other types of block must be entirely processed. This means
+DATA blocks can be resized.
+
+
+3.4. The end-of markers
+
+These blocks are used to delimit parts of an HTX message. It exists two
+markers :
+
+    - end-of-headers (EOH)
+    - end-of-trailers (EOT)
+
+EOH is always present in an HTX message. EOT is optional.
+
+
+4. The HTX API
+
+
+4.1. Get/set HTX message from/to the underlying buffer
+
+The first thing to do to process an HTX message is to get it from the underlying
+buffer. There are 2 functions to do so, the second one relying on the first :
+
+    - htxbuf() returns an HTX message from a buffer. It does not modify the
+      buffer. It only initialize the HTX message if the buffer is empty.
+
+    - htx_from_buf() uses htxbuf(). But it also updates the underlying buffer so
+      that it appears as full.
+
+Both functions return a "zero-sized" HTX message if the buffer is null. This
+way, the HTX message is always valid. The first function is the default function
+to use. The second one is only useful when some content will be added. For
+instance, it used by the HTX analyzers when HAProxy generates a response. Thus,
+the buffer is in a right state.
+
+Once the processing done, if the HTX message has been modified, the underlying
+buffer must be also updated, except htx_from_buf() was used _AND_ data was only
+added. For all other cases, the function htx_to_buf() must be called.
+
+Finally, the function htx_reset() may be called at any time to reset an HTX
+message. And the function buf_room_for_htx_data() may be called to know if a raw
+buffer is full from the HTX perspective. It is used during conversion from/to
+the HTX.
+
+
+4.2. Helpers to deal with free space in an HTX message
+
+Once with an HTX message, following functions may help to process it :
+
+    - htx_used_space() and htx_meta_space() return, respectively, the total
+      space used in an HTX message and the space used by block's metadata only.
+
+    - htx_free_space() and htx_free_data_space() return, respectively, the total
+      free space in an HTX message and the free space available for the payload
+      if a new HTX block is stored (so it is the total free space minus the size
+      of an HTX block).
+
+    - htx_is_empty() and htx_is_not_empty() are boolean functions to know if an
+      HTX message is empty or not.
+
+    - htx_get_max_blksz() returns the maximum size available for the payload,
+      not exceeding a maximum, metadata included.
+
+    - htx_almost_full() should be used to know if an HTX message uses at least
+      3/4 of its capacity.
+
+
+4.3. HTX Blocks manipulations
+
+Once the available sapce in an HTX message is known, the next step is to add HTX
+blocks. First of all the function htx_nbblks() returns the number of blocks
+allocated in an HTX message. Then, there is an add function per block's type :
+
+    - htx_add_stline() adds a start-line. The type (request or response) and the
+      flags of the start-line must be provided, as well as its three parts
+      (method,uri,version or version,status-code,reason).
+
+    - htx_add_header() and htx_add_trailers() are similar. The name and the
+      value must be provided. The inserted HTX block is returned on success or
+      NULL if an error occurred.
+
+    - htx_add_endof() must be used to add any end-of marker. The block's type
+      (EOH or EOT) must be specified. The inserted HTX block is returned on
+      success or NULL if an error occurred.
+
+    - htx_add_all_headers() and htx_add_all_trailers() add, respectively, a list
+      of headers and a list of trailers, followed by the appropriate end-of
+      marker. On success, this marker is returned. Otherwise, NULL is
+      returned. Note there is no rollback on the HTX message when an error
+      occurred. Some headers or trailers may have been added. So it is the
+      caller responsibility to take care of that.
+
+    - htx_add_data() must be used to add a DATA block. Unlike previous
+      functions, this one returns the number of bytes copied or 0 if nothing was
+      copied. If possible, the data are appended to the tail block if it is a
+      DATA block. Only a part of the payload may be copied because this function
+      will try to limit the message defragmentation and the wrapping of blocks
+      as far as possible.
+
+    - htx_add_data_atonce() must be used if all data must be added or nothing.
+      It tries to insert all the payload, this function returns the inserted
+      block on success.  Otherwise it returns NULL.
+
+When an HTX block is added, it is always the last one (the tail). But, if a
+block must be added at a specific place, it is not really handy. 2 functions may
+help (others could be added) :
+
+    - htx_add_last_data() adds a DATA block just after all other DATA blocks and
+      before any trailers and EOT marker. It relies on htx_add_data_atonce(), so
+      a defragmentation may be performed.
+
+    - htx_move_blk_before() moves a specific block just after another one. Both
+      blocks must already be in the HTX message and the block to move must
+      always be placed after the "pivot".
+
+Once added, there are three functions to update the block's payload :
+
+    - htx_replace_stline() updates a start-line. The HTX block must be passed as
+      argument. Only string parts of the start-line are updated by this
+      function. On success, it returns the new start-line. So it is pretty easy
+      to update its flags. NULL is returned if an error occurred.
+
+    - htx_replace_header() fully replaces a header (its name and its value) by a
+      new one. The HTX block must be passed a argument, as well as its new name
+      and its new value. The new header can be smaller or larger than the old
+      one. This function returns the new HTX block on success, or NULL is an
+      error occurred.
+
+    - htx_replace_blk_value() replaces a part of a block's payload or its
+      totality. It works for HEADERS, TRAILERS or DATA blocks. The HTX block
+      must be provided with the part to remove and the new one. The new part can
+      be smaller or larger than the old one. This function returns the new HTX
+      block on success, or NULL is an error occurred.
+
+    - htx_change_blk_value_len() changes the size of the value. It is the caller
+      responsibility to change the value itself, make sure there is enough space
+      and update allocated value. This function updates the HTX message
+      accordingly.
+
+    - htx_set_blk_value_len() changes the size of the value. It is the caller
+      responsibility to change the value itself, make sure there is enough space
+      and update allocated value. Unlike the function
+      htx_change_blk_value_len(), this one does not update the HTX message. So
+      it should be used with caution.
+
+    - htx_cut_data_blk() removes <n> bytes from the beginning of a DATA
+      block. The block's start address and its length are adjusted, and the
+      htx's total data count is updated. This is used to mark that part of some
+      data were transferred from a DATA block without removing this DATA
+      block. No sanity check is performed, the caller is responsible for doing
+      this exclusively on DATA blocks, and never removing more than the block's
+      size.
+
+    - htx_remove_blk() removes a block from an HTX message. It returns the
+      following block or NULL if it is the tail block.
+
+Finally, a block may be removed using the function htx_remove_blk(). This
+function returns the block following the one removed or NULL if it is the tail
+block.
+
+
+4.4. The HTX start-line
+
+Unlike other HTX blocks, the start-line is a bit special because its payload is
+a structure followed by its three parts :
+
+        +--------+-------+-------+-------+
+        | HTX_SL | PART1 | PART2 | PART3 |
+        +--------+-------+-------+-------+
+
+Some macros and functions may help to manipulate these parts :
+
+    - HTX_SL_P{N}_LEN() and HTX_SL_P{N}_PTR() are macros to get the length of a
+      part and a pointer on it. {N} should be 1, 2 or 3.
+
+    - HTX_SL_REQ_MLEN(), HTX_SL_REQ_ULEN(), HTX_SL_REQ_VLEN(),
+      HTX_SL_REQ_MPTR(), HTX_SL_REQ_UPTR() and HTX_SL_REQ_VPTR() are macros to
+      get info about a request start-line. These macros only wrap HTX_SL_P*
+      ones.
+
+    - HTX_SL_RES_VLEN(), HTX_SL_RES_CLEN(), HTX_SL_RES_RLEN(),
+      HTX_SL_RES_VPTR(), HTX_SL_RES_CPTR() and HTX_SL_RES_RPTR() are macros to
+      get info about a response start-line. These macros only wrap HTX_SL_P*
+      ones.
+
+    - htx_sl_p1(), htx_sl_p2() and htx_sl_p2() are functions to get the ist
+      corresponding to the right part of a start-line.
+
+    - htx_sl_req_meth(), htx_sl_req_uri() and htx_sl_req_vsn() get the ist
+      corresponding to the right part of a request start-line.
+
+    - htx_sl_res_vsn(), htx_sl_res_code() and htx_sl_res_reason() get the ist
+      corresponding to the right part of a response start-line.
+
+
+4.5. Iterate on the HTX message
+
+To iterate on an HTX message, the first thing to do is to get the HTX block to
+start the loop. There are three special blocks in an HTX message that may be
+good candidates to start a loop :
+
+    - the head block. It is the oldest inserted block. Multiplexers always start
+      to consume an HTX message from this block. The function htx_get_head()
+      returns its position and htx_get_head_blk() returns the blocks itself. In
+      addition, the function htx_get_head_type() returns its block's type.
+
+    - the tail block. It is the newest inserted block. The function
+      htx_get_tail() returns its position and htx_get_tail_blk() returns the
+      blocks itself. In addition, the function htx_get_tail_type() returns its
+      block's type.
+
+    - the first block. It is the block where to (re)start the analyse. It is
+      used as start point by HTX analyzers. The function htx_get_first() returns
+      its position and htx_get_first_blk() returns the blocks itself. In
+      addition, the function htx_get_first_type() returns its block's type.
+
+For all these functions, if the HTX message is empty, -1 is returned for the
+block's position, NULL instead of a block and HTX_BLK_UNUSED for its type.
+
+Then to iterate on blocks, foreword or backward :
+
+    - htx_get_prev() and htx_get_next() return, respectively, the position of
+      the previous block or the next block, given a specific position. Or -1 if
+      an edge is reached.
+
+    - htx_get_prev_blk() and htx_get_next_blk() return, respectively, the
+      previous block or the next one, given a specific block. Or NULL if an edge
+      is reached.
+
+4.6. Access block content and info
+
+Following functions may be used to retrieve information about a specific HTX
+block :
+
+    - htx_get_blk_pos() returns the position of a block. It must be in the HTX
+      message.
+
+    - htx_get_blk_ptr() returns a pointer on the payload of a block.
+
+    - htx_get_blk_type() returns the type of a block.
+
+    - htx_get_blksz() returns the payload size of a block
+
+    - htx_get_blk_name() returns the name of a block, only if it is a header or
+      a trailer. Otherwise, it returns an empty string.
+
+    - htx_get_blk_value() returns the value of a block, depending on its
+      type. For header and trailer blocks, it is the value field. For markers
+      (EOH or EOT), an empty string is returned. For other blocks an ist
+      pointing on the block payload is returned.
+
+    - htx_is_unique_blk() may be used to know if a block is the only one
+      remaining inside an HTX message, excluding unused blocks. This function is
+      pretty useful to determine the end of a HTX message, in conjunction with
+      HTX_FL_EOM flag.
+
+4.7. Advanced functions
+
+Some more advanced functions may be used to do complex processing on the HTX
+message. These functions are used by HTX analyzers or by multiplexers.
+
+    - htx_truncate() removes all blocks after the one containing a specific
+      offset relatively to the head block of the HTX message. If the offset is
+      inside a DATA block, it is truncated. For all other blocks, the removal
+      starts to the next block.
+
+    - htx_drain() tries to remove a specific amount of bytes of payload. If the
+      tail block is a DATA block, it may be truncated if necessary. All other
+      block are removed at once or kept. This function returns a mixed value,
+      with the first block not removed, or NULL if everything was removed, and
+      the amount of data drained.
+
+    - htx_xfer_blks() transfers HTX blocks from an HTX message to another,
+      stopping on the first block of a specified type or when a specific amount
+      of bytes, including meta-data, was moved. If the tail block is a DATA
+      block, it may be partially moved. All other block are transferred at once
+      or kept. This function returns a mixed value, with the last block moved,
+      or NULL if nothing was moved, and the amount of data transferred. When
+      HEADERS or TRAILERS blocks must be transferred, this function transfers
+      all of them. Otherwise, if it is not possible, it triggers an error. It is
+      the caller responsibility to transfer all headers or trailers at once.
+
+    - htx_append_msg() append an HTX message to another one. All the message is
+      copied or nothing. So, if an error occurred, a rollback is performed. This
+      function returns 1 on success and 0 on error.
+
+    - htx_reserve_max_data() Reserves the maximum possible size for an HTX data
+      block, by extending an existing one or by creating a new one. It returns a
+      compound result with the HTX block and the position where new data must be
+      inserted (0 for a new block). If an error occurs or if there is no space
+      left, NULL is returned instead of a pointer on an HTX block.
+
+    - htx_find_offset() looks for the HTX block containing a specific offset,
+      starting at the HTX message's head. The function returns the found HTX
+      block and the position inside this block where the offset is. If the
+      offset is outside of the HTX message, NULL is returned.
+
+    - htx_defrag() defragments an HTX message. It removes unused blocks and
+      unwraps the payloads part. A temporary buffer is used to do so. This
+      function never fails. A referenced block may be provided. If so, the
+      corresponding new block is returned. Otherwise, NULL is returned.