path: root/buffer_tree.h

/* SPDX-License-Identifier: GPL-2.0 */

/** \file buffer_tree.h Buffer trees, buffer tree nodes and buffer pools.
 *
 * The buffer tree API offers an efficient method for managing the data flow
 * from a producer (e.g. the network receiver) to the consumer(s) (e.g. a sound
 * card).
 *
 * A buffer tree consists of buffer tree nodes which are linked together via
 * parent/child relationships. Data buffers are propagated down without copying.
 *
 * Each data buffer starts its way at the root of the buffer tree. At each
 * node the data is investigated and possibly changed. New data is then fed
 * to each child. There are no file descriptors, no processes/threads and
 * no read or write system calls.
 *
 * Whenever a node in the buffer tree creates output, either by creating a new
 * buffer or by pushing down buffers received from its parent, references to
 * that buffer are created for all children of the node. The code avoids to
 * copy buffer contents when possible.
 *
 * Communication between nodes is possible via the btr_exec_up() function. For
 * example, the alsa writer of para_audiod(1) asks all parent nodes for the
 * number of channels and the sample rate of the current audio file.
 *
 * Buffer pools - An alternative to malloc/free buffer management.
 *
 * Non-leaf nodes create, by definition, output to be processed by their
 * child nodes. The data must be fed through the output channel(s) of the
 * node in order to make that data available to each child.
 *
 * The easiest way to do so is to malloc() a buffer, fill it, and then call
 * btr_add_output(). This adds references to that buffer to all children. The
 * buffer is automatically freed if no buffer tree node is using it any more.
 *
 * This approach is simple but has some drawbacks. For one, the data source
 * represented by the root node does not know in advance how much data will
 * be available. Therefore the allocated buffer will either be larger than
 * necessary or too small so that multiple buffers have to be used.
 *
 * While this could be worked around by using a large buffer and calling
 * realloc() afterwards to shrink the buffer according to how much has been
 * read, there is a second problem which comes from the alignment constraints
 * of some filters, mainly the decoders like mp3dec. These need a minimal
 * amount of data to proceed, and most of them even need this amount as one
 * contiguous buffer, i.e. not spread out over two or more buffers.
 *
 * Although the buffer tree code handles this case just fine, it can be
 * expensive because two or more buffers must be merged by copying buffer
 * contents around in order to satisfy the constraint.
 *
 * This is where buffer pools come into play. Buffer pools try to satisfy
 * alignment constraints without copying buffer content whenever possible. To
 * avoid spreading out the input data over the address space like in the
 * malloc/free approach, a fixed large contiguous buffer (the area) is used
 * instead. A buffer pool consists basically of an area and two pointers
 * called the read head and the write head.
 *
 * Once a buffer pool has been created, its node, e.g. a receiver, obtains the
 * current value of the write head and writes new data to this location. Then
 * it calls btr_add_output_pool() to tell much data it has written. This
 * advances the write head accordingly, and it also creates references to the
 * newly written part of the area for the children of the node to consume.
 *
 * Child nodes consume data by working through their input queue, which is a
 * list of buffer references. Once the content of a buffer is no longer needed
 * by a child node, the child calls btr_consume() to indicate the amount of
 * data which can be dropped from the child's point of view. If no reference
 * to some region of the buffer pool area remains, the read head of the buffer
 * pool advances, making space available for the receiver node to fill.
 *
 * No matter if malloc() or a buffer pool is used, the buffer tree code takes
 * care of alignment constraints imposed by the consumers. In the buffer pool
 * case, automatic merging of references to contiguous buffers is performed.
 * memcpy is only used if a constraint can not be satisfied by using the
 * remaining part of the area only. This only happens when the end of the area
 * is reached.
 */

struct btr_node;
struct btr_pool;

/**
 * The three different types of buffer tree nodes.
 *
 * Usually, there is exactly one node in the buffer tree, the root node, which
 * has no parent. Every node different from the root node has exactly one
 * parent.  The root node represents a data source. Root nodes are thus used by
 * the receivers of paraslash. Also, reading from stdin is realized as the root
 * node of a buffer tree.
 *
 * Each node may have arbitrary many children, including none. Nodes with no
 * children are called leaf nodes. They represent a data sink, like the alsa or
 * the file writer.
 *
 * Hence there are three different types of buffer tree nodes: The root node
 * and the leaf nodes and nodes which have both a parent and at least one
 * child. Such a node is called an internal node.
 *
 * Internal nodes represent filters through which data buffers flow, possibly
 * while being altered on their way to the children of the node. Examples of
 * internal nodes are audio file decoders (mp3dec, oggdec, ...), but also the
 * check for a wav header is implemented as an internal buffer tree node.
 */
enum btr_node_type {
	/* This node has no parent. */
	BTR_NT_ROOT,
	/* Node has parent and at least one child. */
	BTR_NT_INTERNAL,
	/* Node has no children. */
	BTR_NT_LEAF,
};

/**
 * Per node handler used for inter node communication.
 *
 * Each node in the buffer tree may optionally provide a command handler for
 * execution of commands by other nodes of the tree.
 *
 * It is dependent on the node in question which commands are supported and how
 * they work. In any case, the input for the command handler is some string and
 * its output is also a string which is returned via the \a result pointer of
 * the handler.
 *
 * This mechanism is used in para_audiod e.g. by the alsa writer which needs to
 * know the sample rate of its input known to e.g. the mp3dec node further up
 * in the buffer tree.
 */
typedef int (*btr_command_handler)(const struct btr_node *btrn,
		const char *command, char **result);

/**
 * Structure for creating new buffer tree nodes.
 *
 * btr_new_node() takes a pointer to such a structure.
 *
 * There are four different combinations of \a parent and child:
 *
 * 1. both \p NULL. This creates a new buffer tree with a single isolated node.
 *
 * 2. \a parent != \p NULL, \a child == NULL. This creates a new leaf node by
 * adding the new node to the list of children of the given parent node.
 *
 * 3. \a parent == NULL, \a child != NULL. The new node becomes the new root of
 * the buffer tree. The child must be old root.
 *
 * 4. both != NULL. This creates a new internal node. \a child must be child of
 * p. This mode of operation is currently not needed and is thus not yet
 * implemented.
 */
struct btr_node_description {
	/** Name of the new node. */
	const char *name;
	/** Parent of the new node. */
	struct btr_node *parent;
	/** Child of the new node. */
	struct btr_node *child;
	/** Used for inter node communication. Optional. */
	btr_command_handler handler;
	/** Points usually to the struct that contains the node pointer. */
	void *context;
};

size_t btr_pool_size(const struct btr_pool *btrp);
struct btr_pool *btr_pool_new(const char *name, size_t area_size);
void btr_pool_free(struct btr_pool *btrp);
size_t btr_pool_get_buffer(const struct btr_pool *btrp, char **result);
int btr_pool_get_buffers(const struct btr_pool *btrp, struct iovec iov[2]);
void btr_add_output_pool(struct btr_pool *btrp, size_t size,
	struct btr_node *btrn);
size_t btr_pool_unused(const struct btr_pool *btrp);
void btr_copy(const void *src, size_t n, struct btr_pool *btrp,
	struct btr_node *btrn);
struct btr_node *btr_new_node(struct btr_node_description *bnd);
void btr_remove_node(struct btr_node **btrnp);
void btr_add_output(char *buf, size_t size, struct btr_node *btrn);
void btr_add_output_dont_free(const char *buf, size_t size, struct btr_node *btrn);
size_t btr_get_input_queue_size(const struct btr_node *btrn);
size_t btr_get_output_queue_size(const struct btr_node *btrn);
bool btr_no_parent(const struct btr_node *btrn);
size_t btr_next_buffer(const struct btr_node *btrn, char **bufp);
size_t btr_next_buffer_omit(const struct btr_node *btrn, size_t omit,
		char **bufp);
void btr_consume(struct btr_node *btrn, size_t numbytes);
int btr_exec_up(const struct btr_node *btrn, const char *command, char **value_result);
void btr_splice_out_node(struct btr_node **btrnp);
void btr_pushdown(struct btr_node *btrn);
void *btr_context(const struct btr_node *btrn);
void btr_merge(struct btr_node *btrn, size_t dest_size);
void btr_log_tree(const struct btr_node *btrn, int ll);
void btr_pushdown_one(struct btr_node *btrn);
bool btr_inplace_ok(const struct btr_node *btrn);
int btr_node_status(const struct btr_node *btrn, size_t min_iqs,
		enum btr_node_type type);
void btr_get_node_start(const struct btr_node *btrn, struct timeval *tv);
struct btr_node *btr_search_node(const char *name, struct btr_node *root);
void btr_drain(struct btr_node *btrn);
struct btr_node *btr_parent(const struct btr_node *btrn);