Buffer tree management. More...

Data Structures
struct	btr_node_description
	Structure for creating new buffer tree nodes. More...

Typedefs
typedef int(*	btr_command_handler) (const struct btr_node btrn, const char command, char **result)
	Per node handler used for inter node communication. More...

Enumerations
enum	btr_node_type { BTR_NT_ROOT, BTR_NT_INTERNAL, BTR_NT_LEAF }
	The three different types of buffer tree nodes. More...

Functions
size_t	btr_pool_size (const struct btr_pool *btrp)
	Return the size of the buffer pool area. More...

struct btr_pool *	btr_pool_new (const char *name, size_t area_size)
	Create a new buffer pool. More...

void	btr_pool_free (struct btr_pool *btrp)
	Deallocate resources used by a buffer pool. More...

size_t	btr_pool_get_buffer (const struct btr_pool btrp, char *result)
	Obtain the current write head. More...

int	btr_pool_get_buffers (const struct btr_pool *btrp, struct iovec iov[2])
	Get references to buffers pointing to free space of the buffer pool area. More...

void	btr_add_output_pool (struct btr_pool btrp, size_t size, struct btr_node btrn)
	Feed data to child nodes of a buffer tree node. More...

size_t	btr_pool_unused (const struct btr_pool *btrp)
	Get the number of unused bytes in the buffer pool. More...

void	btr_copy (const void src, size_t n, struct btr_pool btrp, struct btr_node *btrn)
	Copy data to write head of a buffer pool and feed it to all children nodes. More...

struct btr_node *	btr_new_node (struct btr_node_description *bnd)
	Create a new buffer tree node. More...

void	btr_remove_node (struct btr_node **btrnp)
	Remove a node from a buffer tree. More...

void	btr_add_output (char buf, size_t size, struct btr_node btrn)
	Insert a malloced buffer into the buffer tree. More...

void	btr_add_output_dont_free (const char buf, size_t size, struct btr_node btrn)
	Insert a buffer into the buffer tree, non-freeing variant. More...

size_t	btr_get_input_queue_size (const struct btr_node *btrn)
	Return the amount of available input bytes of a buffer tree node. More...

size_t	btr_get_output_queue_size (const struct btr_node *btrn)
	Return number of queued output bytes of a buffer tree node. More...

bool	btr_no_parent (const struct btr_node *btrn)
	Find out whether a node is an orphan. More...

size_t	btr_next_buffer (const struct btr_node btrn, char *bufp)
	Obtain the next buffer of the input queue of a buffer tree node. More...

size_t	btr_next_buffer_omit (const struct btr_node btrn, size_t omit, char *bufp)
	Obtain the next buffer of the input queue, omitting data. More...

void	btr_consume (struct btr_node *btrn, size_t numbytes)
	Deallocate the given number of bytes from the input queue. More...

int	btr_exec_up (const struct btr_node btrn, const char command, char **value_result)
	Execute an inter-node command on the given node or on a parent node. More...

void	btr_splice_out_node (struct btr_node **btrnp)
	Remove a node from the buffer tree, reconnecting parent and children. More...

void	btr_pushdown (struct btr_node *btrn)
	Feed all buffer references of the input queue through the output channel. More...

void *	btr_context (const struct btr_node *btrn)
	Obtain the context of a buffer node tree. More...

void	btr_merge (struct btr_node *btrn, size_t dest_size)
	Combine input queue buffers. More...

void	btr_log_tree (const struct btr_node *btrn, int ll)
	Write the current buffer (sub-)tree to the log. More...

void	btr_pushdown_one (struct btr_node *btrn)
	Feed the next buffer of the input queue through the output channel. More...

bool	btr_inplace_ok (const struct btr_node *btrn)
	Find out whether it is OK to change an input buffer. More...

int	btr_node_status (const struct btr_node *btrn, size_t min_iqs, enum btr_node_type type)
	Return the current state of a buffer tree node. More...

void	btr_get_node_start (const struct btr_node btrn, struct timeval tv)
	Get the time of the first I/O for a buffer tree node. More...

struct btr_node *	btr_search_node (const char name, struct btr_node root)
	Find the node with the given name in the buffer tree. More...

void	btr_drain (struct btr_node *btrn)
	Clear the input queue of a buffer tree node. More...

struct btr_node *	btr_parent (const struct btr_node *btrn)
	Get the parent node of a buffer tree node. More...

Detailed Description

Buffer tree management.

Buffer trees and buffer tree nodes.

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 from 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 calls to read() or write().

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, in para_audiod the alsa writer 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 usually create 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 example 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, 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.

Typedef Documentation

◆ btr_command_handler

typedef int(* btr_command_handler) (const struct btr_node *btrn, const char *command, char **result)

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 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.

Enumeration Type Documentation

◆ btr_node_type

enum btr_node_type

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.

Enumerator
BTR_NT_ROOT
BTR_NT_INTERNAL
BTR_NT_LEAF

Function Documentation

◆ btr_pool_size()

size_t btr_pool_size ( const struct btr_pool * btrp )

Return the size of the buffer pool area.

Parameters

btrp	The buffer pool.

Returns: The same value which was passed during creation time to btr_pool_new().

Referenced by btr_pool_unused().

◆ btr_pool_new()

struct btr_pool* btr_pool_new	(	const char *	name,
		size_t	area_size
	)

Create a new buffer pool.

Parameters

name	The name of the new buffer pool.
area_size	The size in bytes of the pool area.

Returns: An opaque pointer to the newly created buffer pool. It must be passed to btr_pool_free() after it is no longer used to deallocate all resources.

References alloc(), PARA_INFO_LOG, and para_strdup().

◆ btr_pool_free()

void btr_pool_free ( struct btr_pool * btrp )

Deallocate resources used by a buffer pool.

Parameters

btrp	A pointer obtained via btr_pool_new().

◆ btr_pool_get_buffer()

size_t btr_pool_get_buffer	(	const struct btr_pool *	btrp,
		char **	result
	)

Obtain the current write head.

Parameters

btrp	The buffer pool.
result	The write head is returned here.

Returns: The maximal amount of bytes that may be written to the returned buffer.

Referenced by btr_copy(), and btr_pool_get_buffers().

◆ btr_pool_get_buffers()

int btr_pool_get_buffers	(	const struct btr_pool *	btrp,
		struct iovec	iov[2]
	)

Get references to buffers pointing to free space of the buffer pool area.

Parameters

btrp	The buffer pool.
iov	The scatter array.

Returns: Zero if the buffer pool is full, one if the free space of the buffer pool area is available as a single contiguous buffer, two if the free space consists of two buffers. If this function returns the value n, then n elements of iov are initialized.

References btr_pool_get_buffer(), and btr_pool_unused().

◆ btr_add_output_pool()

void btr_add_output_pool	(	struct btr_pool *	btrp,
		size_t	size,
		struct btr_node *	btrn
	)

Feed data to child nodes of a buffer tree node.

Parameters

btrp	The buffer pool.
size	The number of bytes to be allocated and fed to each child.
btrn	The node whose children are to be fed.

This function allocates the amount of bytes from the buffer pool area, starting at the current value of the write head, and creates buffer references to the resulting part of the buffer pool area, one for each child of btrn. The references are then fed into the input queue of each child.

Referenced by btr_copy().

◆ btr_pool_unused()

size_t btr_pool_unused ( const struct btr_pool * btrp )

Get the number of unused bytes in the buffer pool.

Parameters

btrp The pool.

Returns: The number of bytes that can currently be allocated.

Note that in general the returned number of bytes is not available as a single contiguous buffer. Use btr_pool_available() to obtain the length of the largest contiguous buffer that can currently be allocated from the buffer pool.

References btr_pool_size().

Referenced by btr_copy(), and btr_pool_get_buffers().

◆ btr_copy()

void btr_copy	(	const void *	src,
		size_t	n,
		struct btr_pool *	btrp,
		struct btr_node *	btrn
	)

Copy data to write head of a buffer pool and feed it to all children nodes.

Parameters

src	The source buffer.
n	The size of the source buffer in bytes.
btrp	The destination buffer pool.
btrn	Add the data as output of this node.

This is expensive. The caller must make sure the data fits into the buffer pool area.

References btr_add_output_pool(), btr_pool_get_buffer(), btr_pool_unused(), and PARA_MIN.

◆ btr_new_node()

struct btr_node* btr_new_node ( struct btr_node_description * bnd )

Create a new buffer tree node.

Parameters

bnd	Specifies how to create the new node.

Returns: A pointer to the newly allocated node.

This function always succeeds (or calls exit()). The returned pointer must be freed using btr_free_node() after the node has been removed from the buffer tree via btr_remove_node().

References alloc(), btr_node_description::context, btr_node_description::handler, btr_node_description::name, para_strdup(), and btr_node_description::parent.

Referenced by check_wav_init(), and register_writer_node().

◆ btr_remove_node()

void btr_remove_node ( struct btr_node ** btrnp )

Remove a node from a buffer tree.

Parameters

btrnp Determines the node to remove.

This orphans all children of the node given by btrnp and removes this node from the child list of its parent. Moreover, the input queue is flushed and the node pointer given by btrp is set to NULL.

See also: btr_splice_out_node.

References btr_drain(), FOR_EACH_CHILD, and PARA_INFO_LOG.

Referenced by i9e_attach_to_stdout().

◆ btr_add_output()

void btr_add_output	(	char *	buf,
		size_t	size,
		struct btr_node *	btrn
	)

Insert a malloced buffer into the buffer tree.

Parameters

buf	The buffer to insert.
size	The size of buf in bytes.
btrn	Position in the buffer tree to create the output.

This creates references to buf and adds these references to each child of btrn. The buffer will be freed using standard free() once no buffer tree node is referencing it any more.

Note that this function must not be used if buf was obtained from a buffer pool. Use btr_add_output_pool() in this case.

◆ btr_add_output_dont_free()

void btr_add_output_dont_free	(	const char *	buf,
		size_t	size,
		struct btr_node *	btrn
	)

Insert a buffer into the buffer tree, non-freeing variant.

Parameters

buf	See btr_add_output().
size	See btr_add_output().
btrn	See btr_add_output().

This is similar to btr_add_output() but additionally sets the dont_free flag on buf. If the refcount for the buffer drops to zero, buf will not be deallocated if this flag is set.

The dont_free bit also prevents the children of btrn from modifying the buffer contents inplace. Specifically, btr_inplace_ok() returns false if there is any buffer in the input queue with the dont_free bit set.

◆ btr_get_input_queue_size()

size_t btr_get_input_queue_size ( const struct btr_node * btrn )

Return the amount of available input bytes of a buffer tree node.

Parameters

btrn	The node whose input size should be computed.

Returns: The total number of bytes available in the node's input queue.

This simply iterates over all buffer references in the input queue and returns the sum of the sizes of all references.

References FOR_EACH_BUFFER_REF.

Referenced by btr_get_output_queue_size().

◆ btr_get_output_queue_size()

size_t btr_get_output_queue_size ( const struct btr_node * btrn )

Return number of queued output bytes of a buffer tree node.

Parameters

btrn	The node whose output queue size should be computed.

Returns: This function iterates over all children of the given node and returns the size of the largest input queue.

References btr_get_input_queue_size(), FOR_EACH_CHILD, and PARA_MAX.

◆ btr_no_parent()

bool btr_no_parent ( const struct btr_node * btrn )

Find out whether a node is an orphan.

Parameters

btrn	The buffer tree node.

Returns: True if btrn has no parent.

This function returns true for the root node and false for any other node.

After a (non-leaf) node was removed removed from the tree, the function returns true for all child nodes.

◆ btr_next_buffer()

size_t btr_next_buffer	(	const struct btr_node *	btrn,
		char **	bufp
	)

Obtain the next buffer of the input queue of a buffer tree node.

Parameters

btrn	The node whose input queue is to be queried.
bufp	Result pointer.

Returns: The number of bytes that can be read from buf.

The call of this function is is equivalent to calling btr_next_buffer_omit() with an omit value of zero.

References btr_next_buffer_omit().

Referenced by check_wav_post_monitor().

◆ btr_next_buffer_omit()

size_t btr_next_buffer_omit	(	const struct btr_node *	btrn,
		size_t	omit,
		char **	bufp
	)

Obtain the next buffer of the input queue, omitting data.

Parameters

btrn	The node whose input queue is to be queried.
omit	Number of bytes to be omitted.
bufp	Result pointer. It is OK to pass `NULL` here.

If a buffer tree node needs more input data but can not consume the data it already has (because it might be needed again later) this function can be used instead of btr_next_buffer() to get a reference to the buffer obtained by skipping the given number of bytes. Skipped input bytes are not consumed.

With a zero omit argument, this function is equivalent to btr_next_buffer().

Returns: Number of bytes in bufp. If there are less than or equal to omit many bytes available in the input queue of the buffer tree node pointed to by btrn, the function returns zero and the value of bufp is undefined.

Referenced by btr_next_buffer().

◆ btr_consume()

void btr_consume	(	struct btr_node *	btrn,
		size_t	numbytes
	)

Deallocate the given number of bytes from the input queue.

Parameters

btrn	The buffer tree node.
numbytes	The number of bytes to be deallocated.

This function must be used to get rid of existing buffer references in the node's input queue. If no references to a buffer remain, the underlying buffers are either freed (in the non-buffer pool case) or the read head of the buffer pool is being advanced.

Note that numbytes may be smaller than the buffer size. In this case the buffer is not deallocated and subsequent calls to btr_next_buffer() return the remaining part of the buffer.

◆ btr_exec_up()

int btr_exec_up	(	const struct btr_node *	btrn,
		const char *	command,
		char **	value_result
	)

Execute an inter-node command on the given node or on a parent node.

Parameters

btrn	The node to start looking.
command	The command to execute.
value_result	Additional arguments and result value.

This function traverses the buffer tree from btrn upwards and looks for the first node that understands command. On this node command is executed, and the result is stored in value_result.

Returns: -ENOTSUP if no parent node of btrn understands command. Otherwise the return value of the command handler is returned.

See also: receiver::execute, filter::execute, writer::execute.

References ERRNO_TO_PARA_ERROR, and PARA_INFO_LOG.

◆ btr_splice_out_node()

void btr_splice_out_node ( struct btr_node ** btrnp )

Remove a node from the buffer tree, reconnecting parent and children.

Parameters

btrnp The node to splice out.

This function is used by buffer tree nodes that do not exist during the whole lifetime of the buffer tree. Unlike btr_remove_node(), calling btr_splice_out_node() does not split the tree into disconnected components but reconnects the buffer tree by making all child nodes of btrn children of the parent of btrn.

References btr_pushdown(), and PARA_NOTICE_LOG.

◆ btr_pushdown()

void btr_pushdown ( struct btr_node * btrn )

Feed all buffer references of the input queue through the output channel.

Parameters

btrn	The node whose buffer references should be pushed down.

This function is useful for filters that do not change the contents of the buffers at all, like the wav filter or the amp filter if no amplification was specified. This function is rather cheap.

See also: btr_pushdown_one().

References FOR_EACH_BUFFER_REF_SAFE.

Referenced by btr_splice_out_node().

◆ btr_context()

void* btr_context ( const struct btr_node * btrn )

Obtain the context of a buffer node tree.

Parameters

btrn	The node whose output queue size should be computed.

Returns: A pointer to the context address specified at node creation time.

See also: btr_new_node(), struct btr_node_description.

◆ btr_merge()

void btr_merge	(	struct btr_node *	btrn,
		size_t	dest_size
	)

Combine input queue buffers.

Parameters

btrn	The buffer tree node whose input should be merged.
dest_size	Stop merging if a buffer of at least this size exists.

Used to combine as many buffers as needed into a single buffer whose size is at least dest_size. This function is rather cheap in case the parent node uses buffer pools and rather expensive otherwise.

Note that if less than dest_size bytes are available in total, this function does nothing and subsequent calls to btr_next_buffer() will still return a buffer size less than dest_size.

Referenced by check_wav_post_monitor().

◆ btr_log_tree()

void btr_log_tree	(	const struct btr_node *	btrn,
		int	loglevel
	)

Write the current buffer (sub-)tree to the log.

Parameters

btrn	Start logging at this node.
loglevel	Set severity with which the tree should be logged.

◆ btr_pushdown_one()

void btr_pushdown_one ( struct btr_node * btrn )

Feed the next buffer of the input queue through the output channel.

Parameters

btrn	The node whose first input queue buffer should be pushed down.

This works like btr_pushdown() but pushes down only one buffer reference.

◆ btr_inplace_ok()

bool btr_inplace_ok ( const struct btr_node * btrn )

Find out whether it is OK to change an input buffer.

Parameters

btrn	The buffer tree node to check.

This is used by filters that produce exactly the same amount of output as there is input. The amp filter which multiplies each sample by some number is an example of such a filter. If there are no other nodes in the buffer tree that read the same input stream (i.e. if btrn has no siblings), a node may modify its input buffer directly and push down the modified buffer to its children, thereby avoiding to allocate a possibly large additional buffer.

Since the buffer tree may change at any time, this function should be called during each post_monitor call.

Returns: True if btrn has no siblings.

References FOR_EACH_BUFFER_REF.

◆ btr_node_status()

int btr_node_status	(	const struct btr_node *	btrn,
		size_t	min_iqs,
		enum btr_node_type	type
	)

Return the current state of a buffer tree node.

Parameters

btrn	The node whose state should be queried.
min_iqs	The minimal input queue size.
type	The supposed type of btrn.

Most users of the buffer tree subsystem call this function from both their ->pre_monitor() and ->post_monitor() methods.

Returns: Negative if an error condition was detected, zero if there is nothing to do and positive otherwise.

Examples:

If a non-root node has no parent and an empty input queue, the function returns -E_BTR_EOF. Similarly, if a non-leaf node has no children, -E_BTR_NO_CHILD is returned.
If less than min_iqs many bytes are available in the input queue and no EOF condition was detected, the function returns zero.
If there's plenty of data left in the input queue of the children of btrn, the function also returns zero in order to bound the memory usage of the buffer tree.

References BTR_NT_LEAF.

Referenced by check_wav_post_monitor(), check_wav_pre_monitor(), generic_filter_pre_monitor(), and generic_recv_pre_monitor().

◆ btr_get_node_start()

void btr_get_node_start	(	const struct btr_node *	btrn,
		struct timeval *	tv
	)

Get the time of the first I/O for a buffer tree node.

Parameters

btrn	The node whose I/O time should be obtained.
tv	Result pointer.

Mainly useful for the time display of para_audiod.

Referenced by audiod_get_btr_root().

◆ btr_search_node()

struct btr_node* btr_search_node	(	const char *	name,
		struct btr_node *	root
	)

Find the node with the given name in the buffer tree.

Parameters

name	The name of the node to search.
root	Where to start the search.

Returns: A pointer to the node with the given name on success. If name is NULL, the function returns root. If there is no node with the given name, NULL is returned.

References btr_search_node(), and FOR_EACH_CHILD.

Referenced by btr_search_node().

◆ btr_drain()

void btr_drain ( struct btr_node * btrn )

Clear the input queue of a buffer tree node.

Parameters

btrn	The node whose input queue should be cleared.

References FOR_EACH_BUFFER_REF_SAFE.

Referenced by btr_remove_node().

◆ btr_parent()

struct btr_node* btr_parent ( const struct btr_node * btrn )

Get the parent node of a buffer tree node.

Parameters

btrn	The node whose parent should be returned.

btrn must not be NULL.

Returns: The parent of btrn, or NULL if btrn is the root node of the buffer tree.

	Paraslash Audio Streaming
	About News Download Documentation Development

Data Structures

Typedefs

Enumerations

Functions

Detailed Description

Typedef Documentation

◆ btr_command_handler

Enumeration Type Documentation

◆ btr_node_type

Function Documentation

◆ btr_pool_size()

◆ btr_pool_new()

◆ btr_pool_free()

◆ btr_pool_get_buffer()

◆ btr_pool_get_buffers()

◆ btr_add_output_pool()

◆ btr_pool_unused()

◆ btr_copy()

◆ btr_new_node()

◆ btr_remove_node()

◆ btr_add_output()

◆ btr_add_output_dont_free()

◆ btr_get_input_queue_size()

◆ btr_get_output_queue_size()

◆ btr_no_parent()

◆ btr_next_buffer()

◆ btr_next_buffer_omit()

◆ btr_consume()

◆ btr_exec_up()

◆ btr_splice_out_node()

◆ btr_pushdown()

◆ btr_context()

◆ btr_merge()

◆ btr_log_tree()

◆ btr_pushdown_one()

◆ btr_inplace_ok()

◆ btr_node_status()

◆ btr_get_node_start()

◆ btr_search_node()

◆ btr_drain()

◆ btr_parent()