buffer_tree.h

   1 /* Copyright (C) 2009 Andre Noll <maan@tuebingen.mpg.de>, see file COPYING. */
   2
   3 /**
   4  * \file buffer_tree.h Buffer tree management.
   5  *
   6  * \par Buffer trees and buffer tree nodes.
   7  * The buffer tree API offers a more powerful method than standard unix pipes
   8  * for managing the data flow from the producer of the data (e.g. the network
   9  * receiver) to its consumer(s) (e.g. a sound card).
  10  *
  11  * A buffer tree consists of buffer tree nodes linked via certain parent/child
  12  * relationships.
  13  *
  14  * Each data buffer starts its way from the root of the buffer tree. At each
  15  * node the data is investigated and possibly changed. New data is then fed to
  16  * each child.  Everything happens within one single-treaded process. There are
  17  * no file descriptors and no calls to read() or write().
  18  *
  19  * Whenever a node in the buffer tree creates output, either by creating a new
  20  * buffer or by pushing down buffers received from its parent, references to
  21  * that buffer are created for all children of the node. The buffer tree code
  22  * tries hard to avoid to copy buffer contents, but is forced to do so in case
  23  * there are alignment constraints.
  24  *
  25  * Communication between nodes is possible via the btr_exec_up() function.
  26  * For example, in para_audiod the alsa writer asks all parent nodes
  27  * for for the number of channels and the sample rate of the current
  28  * audio file.
  29  *
  30  * Buffer pools - An alternative to malloc/free buffer management.
  31  *
  32  * Non-leaf nodes usually create output to be processed by their children.  The
  33  * data must be fed through the output channel(s) of the node in order to make
  34  * that data available to each child.
  35  *
  36  * The easiest way to do so is to malloc() a buffer, fill it, and then call
  37  * btr_add_output(). This adds references to that buffer to all children. The
  38  * buffer is automatically freed if no buffer tree node is using it any more.
  39  *
  40  * This approach, while being simple, has some drawbacks, especially affecting
  41  * the root nodes of the buffer tree. Often the data source which is
  42  * represented by a root node does not know in advance how much data will be
  43  * available.  Therefore the allocated buffer is either larger than what can
  44  * currently be read, or is too small so that multiple buffers have to be used.
  45  *
  46  * While this could be worked around by using a large buffer and calling
  47  * realloc() afterwards to shrink the buffer according to how much has been
  48  * read, there is a second problem which comes from the alignment constraints
  49  * of some filters, mainly the decoders like mp3dec. These need a minimal
  50  * amount of data to proceed, and most of them even need this amount as one
  51  * contiguous buffer, i.e. not spread out over two or more buffers.
  52  *
  53  * Although the buffer tree code handles this case just fine, it can be
  54  * expensive because two or more buffers must be merged by copying buffer
  55  * contents around in order to satisfy the constraint.
  56  *
  57  * This is where buffer pools come into play. Buffer pools try to satisfy
  58  * alignment constraints without copying buffer content whenever possible. To
  59  * avoid spreading out the input data over the address space like in the
  60  * malloc/free approach, a fixed large contiguous buffer (the area) is used
  61  * instead. A buffer pool consists basically of an area and two pointers, the
  62  * read head and the write head.
  63  *
  64  * Once a buffer pool has been created, its node, e.g. a receiver, obtains the
  65  * current value of the write head and writes new data to this location. Then
  66  * it calls btr_add_output_pool() to tell much data it has written. This
  67  * advances the write head accordingly, and it also creates references to the
  68  * newly written part of the area for the children of the node to consume.
  69  *
  70  * Child nodes consume data by working through their input queue, which is a
  71  * list of buffer references. Once the content of a buffer is no longer needed
  72  * by a child node, the child calls btr_consume() to indicate the amount of
  73  * data which can be dropped from the child's point of view. If no reference
  74  * to some region of the buffer pool area remains, the read head of the buffer
  75  * pool advances, making space available for the receiver node to fill.
  76  *
  77  * No matter if malloc() or a buffer pool is used, the buffer tree code takes
  78  * care of alignment constraints imposed by the consumers. In the buffer pool
  79  * case, automatic merging of references to contiguous buffers is performed.
  80  * memcpy is only used if a constraint can not be satisfied by using the
  81  * remaining part of the area only. This only happens when the end of the area
  82  * is reached.
  83  */
  84
  85 struct btr_node;
  86 struct btr_pool;
  87
  88 /**
  89  * The three different types of buffer tree nodes.
  90  *
  91  * Usually, there is exactly one node in the buffer tree, the root node, which
  92  * has no parent. Every node different from the root node has exactly one
  93  * parent.  The root node represents a data source. Root nodes are thus used by
  94  * the receivers of paraslash. Also, reading from stdin is realized as the root
  95  * node of a buffer tree.
  96  *
  97  * Each node may have arbitrary many children, including none. Nodes with no
  98  * children are called leaf nodes. They represent a data sink, like the alsa or
  99  * the file writer.
 100  *
 101  * Hence there are three different types of buffer tree nodes: The root node
 102  * and the leaf nodes and nodes which have both a parent and at least one
 103  * child. Such a node is called an internal node.
 104  *
 105  * Internal nodes represent filters through which data buffers flow, possibly
 106  * while being altered on their way to the children of the node. Examples of
 107  * internal nodes are audio file decoders (mp3dec, oggdec, ...), but also the
 108  * check for a wav header is implemented as an internal buffer tree node.
 109  */
 110 enum btr_node_type {
 111         /* This node has no parent. */
 112         BTR_NT_ROOT,
 113         /* Node has parent and at least one child. */
 114         BTR_NT_INTERNAL,
 115         /* Node has no children. */
 116         BTR_NT_LEAF,
 117 };
 118
 119 /**
 120  * Per node handler used for inter node communication.
 121  *
 122  * Each node in the buffer tree may optionally provide a command handler for
 123  * execution of commands by other nodes of the tree.
 124  *
 125  * It is dependent on the node in question which commands are supported and how
 126  * they work. In any case, the input for the command handler is some string and
 127  * its output is also a string which is returned via the \a result pointer of
 128  * the handler.
 129  *
 130  * This mechanism is used in para_audiod e.g. by the alsa writer which needs to
 131  * know the sample rate of its input known to e.g. the mp3dec node further up
 132  * in the buffer tree.
 133  */
 134 typedef int (*btr_command_handler)(struct btr_node *btrn,
 135                 const char *command, char **result);
 136
 137 /**
 138  * Structure for creating new buffer tree nodes.
 139  *
 140  * btr_new_node() takes a pointer to such a structure.
 141  *
 142  * There are four different combinations of \a parent and child:
 143  *
 144  * 1. both \p NULL. This creates a new buffer tree with a single isolated node.
 145  *
 146  * 2. \a parent != \p NULL, \a child == NULL. This creates a new leaf node by
 147  * adding the new node to the list of children of the given parent node.
 148  *
 149  * 3. \a parent == NULL, \a child != NULL. The new node becomes the new root of
 150  * the buffer tree. The child must be old root.
 151  *
 152  * 4. both != NULL. This creates a new internal node. \a child must be child of
 153  * p. This mode of operation is currently not needed and is thus not yet
 154  * implemented.
 155  */
 156 struct btr_node_description {
 157         /** Name of the new node. */
 158         const char *name;
 159         /** Parent of the new node. */
 160         struct btr_node *parent;
 161         /** Child of the new node. */
 162         struct btr_node *child;
 163         /** Used for inter node communication. Optional. */
 164         btr_command_handler handler;
 165         /** Points usually to the struct that contains the node pointer. */
 166         void *context;
 167 };
 168
 169 size_t btr_pool_size(struct btr_pool *btrp);
 170 struct btr_pool *btr_pool_new(const char *name, size_t area_size);
 171 void btr_pool_free(struct btr_pool *btrp);
 172 size_t btr_pool_get_buffer(struct btr_pool *btrp, char **result);
 173 int btr_pool_get_buffers(struct btr_pool *btrp, struct iovec iov[2]);
 174 void btr_add_output_pool(struct btr_pool *btrp, size_t size,
 175         struct btr_node *btrn);
 176 size_t btr_pool_unused(struct btr_pool *btrp);
 177 void btr_copy(const void *src, size_t n, struct btr_pool *btrp,
 178         struct btr_node *btrn);
 179
 180 struct btr_node *btr_new_node(struct btr_node_description *bnd);
 181 void btr_remove_node(struct btr_node **btrnp);
 182 void btr_add_output(char *buf, size_t size, struct btr_node *btrn);
 183 void btr_add_output_dont_free(const char *buf, size_t size, struct btr_node *btrn);
 184 size_t btr_get_input_queue_size(struct btr_node *btrn);
 185 size_t btr_get_output_queue_size(struct btr_node *btrn);
 186 bool btr_no_parent(struct btr_node *btrn);
 187 size_t btr_next_buffer(struct btr_node *btrn, char **bufp);
 188 size_t btr_next_buffer_omit(struct btr_node *btrn, size_t omit, char **bufp);
 189 void btr_consume(struct btr_node *btrn, size_t numbytes);
 190 int btr_exec_up(struct btr_node *btrn, const char *command, char **value_result);
 191 void btr_splice_out_node(struct btr_node **btrnp);
 192 void btr_pushdown(struct btr_node *btrn);
 193 void *btr_context(struct btr_node *btrn);
 194 void btr_merge(struct btr_node *btrn, size_t dest_size);
 195 void btr_log_tree(struct btr_node *btrn, int ll);
 196 void btr_pushdown_one(struct btr_node *btrn);
 197 bool btr_inplace_ok(struct btr_node *btrn);
 198 int btr_node_status(struct btr_node *btrn, size_t min_iqs,
 199                 enum btr_node_type type);
 200 void btr_get_node_start(struct btr_node *btrn, struct timeval *tv);
 201 struct btr_node *btr_search_node(const char *name, struct btr_node *root);
 202 void btr_drain(struct btr_node *btrn);
 203 struct btr_node *btr_parent(struct btr_node *btrn);