X-Git-Url: http://git.tuebingen.mpg.de/?p=paraslash.git;a=blobdiff_plain;f=buffer_tree.h;h=549f95a224e1ede3ec8e5344d8beb87f3fb88e31;hp=785cd27219cafbd1306f3d49269522b0142aa39e;hb=60ef885705932a682097ad2b9f2379282d814e79;hpb=764e787bc065694b2e9b05159a92104d585f59eb diff --git a/buffer_tree.h b/buffer_tree.h index 785cd272..549f95a2 100644 --- a/buffer_tree.h +++ b/buffer_tree.h @@ -1,26 +1,204 @@ +/* + * Copyright (C) 2009-2010 Andre Noll + * + * Licensed under the GPL v2. For licencing details see COPYING. + */ + +/** + * \file buffer_tree.h Buffer tree management. + * + * \par 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. + */ 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)(struct btr_node *btrn, const char *command, char **result); -struct btr_node *btr_new_node(const char *name, struct btr_node *parent, - btr_command_handler handler, void *context); -void btr_del_node(struct btr_node *btrn); +/** + * 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(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(struct btr_pool *btrp, char **result); +int btr_pool_get_buffers(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(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 *btrn); +void btr_free_node(struct btr_node *btrn); void btr_add_output(char *buf, size_t size, struct btr_node *btrn); -bool btr_no_children(struct btr_node *btrn); -size_t btr_bytes_pending(struct btr_node *btrn); size_t btr_get_input_queue_size(struct btr_node *btrn); +size_t btr_get_output_queue_size(struct btr_node *btrn); bool btr_no_parent(struct btr_node *btrn); size_t btr_next_buffer(struct btr_node *btrn, char **bufp); void btr_consume(struct btr_node *btrn, size_t numbytes); -int btr_exec(struct btr_node *btrn, const char *command, char **value_result); int btr_exec_up(struct btr_node *btrn, const char *command, char **value_result); void btr_splice_out_node(struct btr_node *btrn); void btr_pushdown(struct btr_node *btrn); void *btr_context(struct btr_node *btrn); void btr_merge(struct btr_node *btrn, size_t dest_size); -bool btr_eof(struct btr_node *btrn); void btr_log_tree(struct btr_node *btrn, int loglevel); -int btr_pushdown_one(struct btr_node *btrn); +void btr_pushdown_one(struct btr_node *btrn); bool btr_inplace_ok(struct btr_node *btrn); +int btr_node_status(struct btr_node *btrn, size_t min_iqs, + enum btr_node_type type); +void btr_get_node_start(struct btr_node *btrn, struct timeval *tv); +struct btr_node *btr_search_node(const char *name, struct btr_node *root);