paraslash Paraslash Audio Streaming
About   News   Download   Documentation   Development

Data Structures | Typedefs | Enumerations | Functions
buffer_tree.h File Reference

Buffer tree management. More...

Data Structures

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

Typedefs

typedef int(* btr_command_handler) (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 (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 (struct btr_pool *btrp, char **result)
 Obtain the current write head. More...
 
int btr_pool_get_buffers (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 (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 (struct btr_node *btrn)
 Return the amount of available input bytes of a buffer tree node. More...
 
size_t btr_get_output_queue_size (struct btr_node *btrn)
 Return number of queued output bytes of a buffer tree node. More...
 
bool btr_no_parent (struct btr_node *btrn)
 Find out whether a node is an orphan. More...
 
size_t btr_next_buffer (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 (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 (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 (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 (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 (struct btr_node *btrn)
 Find out whether it is OK to change an input buffer. More...
 
int btr_node_status (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 (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 (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 a more powerful method than standard unix pipes for managing the data flow from the producer of the data (e.g. the network receiver) to its consumer(s) (e.g. a sound card).

A buffer tree consists of buffer tree nodes linked via certain parent/child relationships.

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. Everything happens within one single-treaded process. There are no file descriptors 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 buffer tree code tries hard to avoid to copy buffer contents, but is forced to do so in case there are alignment constraints.

Communication between nodes is possible via the btr_exec_up() function. For example, in para_audiod the alsa writer asks all parent nodes for 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 children. 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, while being simple, has some drawbacks, especially affecting the root nodes of the buffer tree. Often the data source which is represented by a root node does not know in advance how much data will be available. Therefore the allocated buffer is either larger than what can currently be read, or is 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) (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

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 ( struct btr_pool *  btrp)

Return the size of the buffer pool area.

Parameters
btrpThe 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
nameThe name of the new buffer pool.
area_sizeThe 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
btrpA pointer obtained via btr_pool_new().

◆ btr_pool_get_buffer()

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

Obtain the current write head.

Parameters
btrpThe buffer pool.
resultThe 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 ( struct btr_pool *  btrp,
struct iovec  iov[2] 
)

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

Parameters
btrpThe buffer pool.
iovThe 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
btrpThe buffer pool.
sizeThe number of bytes to be allocated and fed to each child.
btrnThe 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 ( struct btr_pool *  btrp)

Get the number of unused bytes in the buffer pool.

Parameters
btrpThe 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
srcThe source buffer.
nThe size of the source buffer in bytes.
btrpThe destination buffer pool.
btrnAdd 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
bndSpecifies 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
btrnpDetermines 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
bufThe buffer to insert.
sizeThe size of buf in bytes.
btrnPosition 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
bufSee btr_add_output().
sizeSee btr_add_output().
btrnSee 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 ( struct btr_node *  btrn)

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

Parameters
btrnThe 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 ( struct btr_node *  btrn)

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

Parameters
btrnThe 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 ( struct btr_node *  btrn)

Find out whether a node is an orphan.

Parameters
btrnThe 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 ( struct btr_node *  btrn,
char **  bufp 
)

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

Parameters
btrnThe node whose input queue is to be queried.
bufpResult 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 ( struct btr_node *  btrn,
size_t  omit,
char **  bufp 
)

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

Parameters
btrnThe node whose input queue is to be queried.
omitNumber of bytes to be omitted.
bufpResult 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
btrnThe buffer tree node.
numbytesThe 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 ( 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
btrnThe node to start looking.
commandThe command to execute.
value_resultAdditional 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
btrnpThe 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
btrnThe 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 ( struct btr_node *  btrn)

Obtain the context of a buffer node tree.

Parameters
btrnThe 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
btrnThe buffer tree node whose input should be merged.
dest_sizeStop 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 ( struct btr_node *  btrn,
int  loglevel 
)

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

Parameters
btrnStart logging at this node.
loglevelSet 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
btrnThe 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 ( struct btr_node *  btrn)

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

Parameters
btrnThe 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 ( struct btr_node *  btrn,
size_t  min_iqs,
enum btr_node_type  type 
)

Return the current state of a buffer tree node.

Parameters
btrnThe node whose state should be queried.
min_iqsThe minimal input queue size.
typeThe 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 ( struct btr_node *  btrn,
struct timeval *  tv 
)

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

Parameters
btrnThe node whose I/O time should be obtained.
tvResult 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
nameThe name of the node to search.
rootWhere 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
btrnThe 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 ( struct btr_node *  btrn)

Get the parent node of a buffer tree node.

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