2018-07-13 - HAProxy Internal Buffer API


1. Background

HAProxy uses a "struct buffer" internally to store data received from external
agents, as well as data to be sent to external agents. These buffers are also
used during data transformation such as compression, header insertion or
defragmentation, and are used to carry intermediary representations between the
various internal layers. They support wrapping at the end, and they carry their
own size information so that in theory it would be possible to use different
buffer sizes in parallel even though this is not currently implemented.

The format of this structure has evolved over time, to reach a point where it
is convenient and versatile enough to have permitted to make several internal
types converge into a single one (specifically the struct chunk disappeared).


2. Representation as of 1.9-dev1

The current buffer representation consists in a linear storage area of known
size, with a head position indicating the oldest data, and a total data count
expressed in bytes. The head position, data count and size are expressed as
integers and are positive or null. By convention, the head position is strictly
smaller than the buffer size and the data count is smaller than or equal to the
size, so that wrapping can be resolved with a single subtract. A buffer not
respecting these rules is said to be degenerate. Unless specified otherwise,
the various API functions will adopt an undefined behaviour when passed such a
degenerate buffer.

 Buffer declaration :

    struct buffer {
        size_t size;     // size of the storage area (wrapping point)
        char  *area;     // start of the storage area
        size_t data;     // contents length after head
        size_t head;     // start offset of remaining data relative to area
    };


 Linear buffer representation :

    area
      |
      V<--------------------------------------------------------->| size
      +-----------+---------------------------------+-------------+
      |           |/////////////////////////////////|             |
      +-----------+---------------------------------+-------------+
      |<--------->|<------------------------------->|
           head                 data                ^
                                                    |
                                                   tail


 Wrapping buffer representation :

    area
      |
      V<--------------------------------------------------------->| size
      +---------------+------------------------+------------------+
      |///////////////|                        |//////////////////|
      +---------------+------------------------+------------------+
      |<-------------------------------------->| head
      |-------------->| ...data         data...|<-----------------|
                      ^
                      |
                     tail


3. Terminology

Manipulating a buffer just based on a head and a wrapping data count is not
very convenient, so we define a certain number of terms for important elements
characterizing a buffer :

   - origin    : pointer to relative position 0 in the storage area. Undefined
                 when the buffer is not allocated.

   - size      : the allocated size of the storage area starting at the origin,
                 expressed in bytes. A buffer whose size is zero is said not to
                 be allocated, and its origin in this case is undefined.

   - data      : the amount of data the buffer contains, in bytes. It is always
                 lower than or equal to the buffer's size, hence it is always 0
                 for an unallocated buffer.

   - emptiness : a buffer is said to be empty when it contains no data, hence
                 data == 0. It is possible for such buffers not to be allocated
                 and to have size == 0 as well.

   - room      : the available space in the buffer. This is its size minus data.

   - head      : position relative to origin where the oldest data byte is found
                 (it typically is what send() uses to pick outgoing data). The
                 head is strictly smaller than the size.

   - tail      : position relative to origin where the first spare byte is found
                 (it typically is what recv() uses to store incoming data). It
                 is always equal to the buffer's data added to its head modulo
                 the buffer's size.

   - wrapping  : the byte following the last one of the storage area loops back
                 to position 0. This is called wrapping. The wrapping point is
                 the first position relative to origin which doesn't belong to
                 the storage area. There is no wrapping when a buffer is not
                 allocated. Wrapping requires special care and means that the
                 regular string manipulation functions are not usable on most
                 buffers, unless it is known that no wrapping happens. Free
                 space may wrap as well if the buffer only contains data in the
                 middle.

   - alignment : a buffer is said to be aligned if its data do not wrap. That
                 is, its head is strictly before the tail, or the buffer is
                 empty and the head is null. Aligning a buffer may be required
                 to use regular string manipulation functions which have no
                 support for wrapping.


A buffer may be in three different states :
   - unallocated : size == 0, area == 0 (b_is_null() is true)
   - waiting     : size == 0, area != 0
   - allocated   : size  > 0, area  > 0

It is not permitted to have area == 0 with a non-null size. In addition, the
waiting state may also be used to indicate a read-only buffer which does not
wrap and which must not be freed (e.g. for use with error messages).

The basic API only covers allocated buffers. Switching to/from the other states
is covered by the management API since it requires specific allocation and free
calls.


4. Using buffers

Buffers are defined in a few files :
   - include/common/buf.h    : structure definition, and manipulation functions
   - include/common/buffer.h : resource management (alloc/free/wait lists)
   - include/common/istbuf.h : advanced string manipulation


4.1. Basic API

The basic API is made of the functions which abstract accesses to the buffers
and which help calculating their state, free space or used space.

====================+==================+=======================================
Function            | Arguments/Return | Description
--------------------+------------------+---------------------------------------
b_is_null()         | const buffer *buf| returns true if (and only if) the
                    | ret: int         | buffer is not yet allocated and thus
                    |                  | points to a NULL area
--------------------+------------------+---------------------------------------
b_orig()            | const buffer *buf| returns the pointer to the origin of
                    | ret: char *      | the storage, which is the location of
                    |                  | byte at offset zero. This is mostly
                    |                  | used by functions which handle the
                    |                  | wrapping by themselves
--------------------+------------------+---------------------------------------
b_size()            | const buffer *buf| returns the size of the buffer
                    | ret: size_t      |
--------------------+------------------+---------------------------------------
b_wrap()            | const buffer *buf| returns the pointer to the wrapping
                    | ret: char *      | position of the buffer area, which is
                    |                  | by definition the first byte not part
                    |                  | of the buffer
--------------------+------------------+---------------------------------------
b_data()            | const buffer *buf| returns the number of bytes present in
                    | ret: size_t      | the buffer
--------------------+--------------                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                               