buffer_tree.h

   1 /**
   2  * Buffer trees and buffer tree nodes.
   3  *
   4  * The buffer tree API offers a more powerful method than standard unix pipes
   5  * for managing the data flow from the producer of the data (e.g. the network
   6  * receiver) to its consumer(s) (e.g. a sound card).
   7  *
   8  * Each data buffer starts its way from the root of the buffer tree. At each
   9  * child node the data is investigated and new data is fed to each child.
  10  * Everything happens within one single-treaded process. There are no file
  11  * descriptors, no calls to read() or write().
  12  *
  13  * A buffer tree consists of buffer tree nodes. Usually, there is exactly one
  14  * node in the buffer tree, the root node, which has no parent. Every node
  15  * different from the root node has exactly one parent.
  16  *
  17  * The root node represents a data source. Root nodes are thus used by the
  18  * receivers of paraslash. Also, reading from stdin is realized as the root
  19  * node of a buffer tree.
  20  *
  21  * Each node may have arbitrary many children, including none.  Nodes with no
  22  * children are called leaf nodes. They represent a data sink, like the alsa or
  23  * the file writer.
  24  *
  25  * Hence there are three different types of buffer tree nodes: The root node
  26  * and the leaf nodes and nodes which have both a parent and at least one
  27  * child. Such a node is called an internal node.
  28  *
  29  * Internal nodes represent filters through which data buffers flow, possibly
  30  * while being altered on their way to the children of the node. Examples of
  31  * internal nodes are audio file decoders (mp3dec, oggdec, ...), but also the
  32  * check for a wav header is implemented as an internal buffer tree node.
  33  *
  34  * Whenever a node in the buffer tree creates output, either by creating a new
  35  * buffer or by pushing down buffers received from its parent, references to
  36  * that buffer are created for all children of the node. The buffer tree code
  37  * tries hard to avoid to copy buffer contents, but is forced to do so in case
  38  * there are alignment constraints.
  39  *
  40  * Communication between nodes is possible via the btr_exec_up() function.
  41  * For example, in para_audiod the alsa writer asks all parent nodes
  42  * for for the number of channels and the sample rate of the current
  43  * audio file.
  44  */
  45 struct btr_node;
  46
  47 /**
  48  * Buffer pools - An alternative to malloc/free buffer management.
  49  *
  50  * Non-leaf nodes usually create output to be processed by their children.  The
  51  * data must be fed through the output channel(s) of the node in order to make
  52  * that data available to each child.
  53  *
  54  * The easiest way to do so is to malloc() a buffer, fill it, and then call
  55  * btr_add_output(). This adds references to that buffer to all children. The
  56  * buffer is automatically freed if no buffer tree node is using it any more.
  57  *
  58  * This approach, while simple, has some drawbacks, especially affecting the
  59  * root nodes of the buffer tree. Often the data source which is represented by
  60  * a root node does not know in advance how much data will be available.
  61  * Therefore the allocated buffer is either larger than what can currently be
  62  * read, or is too small so that multiple buffers have to be used.
  63  *
  64  * While this could be worked around by using a large buffer and calling
  65  * realloc() afterwards to shrink the buffer according to how much has been
  66  * read, there is a second problem which comes from the alignment constraints
  67  * of some filters, mainly the decoders. These need a minimal amount of data to
  68  * proceed, and most of them even need this amount as one contiguous buffer,
  69  * i.e.  not spread out over two or more buffers.
  70  *
  71  * Although the buffer tree code handles this case just fine, it can be
  72  * expensive because two or more buffers must be combined by copying buffer
  73  * contents around in order to satisfy the constraint.
  74  *
  75  * This is where buffer pools come into play. Buffer pools try to satisfy
  76  * alignment constraints without copying buffer content whenever possible. To
  77  * avoid spreading out the input data over the address space like in the
  78  * malloc/free approach, a fixed large contiguous buffer (the area) is used
  79  * instead. A buffer pool consists basically of an area and two pointers, the
  80  * read head and the write head.
  81  *
  82  * Once a buffer pool has been created, its node, e.g. a receiver, obtains the
  83  * current value of the write head and writes new data to this location. Then
  84  * it calls btr_add_output_pool() to tell much data it has written. This
  85  * advances the write head accordingly, and it also creates references to the
  86  * newly written part of the area for the children of the node to consume.
  87  *
  88  * Child nodes consume data by working through their input queue, which is a
  89  * list of buffer references. Once the content of a buffer is no longer needed
  90  * by a child node, the child calls btr_consume() to indicate the amount of
  91  * data which can be dropped from the child's point of view.  If no reference
  92  * to some region of the buffer pool area remains, the read head of the buffer
  93  * pool advances, making space available for the receiver node to fill.
  94  *
  95  * No matter if malloc() or a buffer pool is used, the buffer tree code takes
  96  * care of alignment constraints imposed by the consumers. In the buffer pool
  97  * case, automatic merging of references to contiguous buffers is performed.
  98  * memcpy is only used if a constraint can not be satisfied by using the
  99  * remaining part of the area only. This only happens when the end of the area
 100  * is reached.
 101  */
 102
 103 struct btr_pool;
 104 typedef int (*btr_command_handler)(struct btr_node *btrn,
 105                 const char *command, char **result);
 106
 107 enum btr_node_type {
 108         BTR_NT_ROOT,
 109         BTR_NT_INTERNAL,
 110         BTR_NT_LEAF,
 111 };
 112
 113 struct btr_node_description {
 114         const char *name;
 115         struct btr_node *parent;
 116         btr_command_handler handler;
 117         void *context;
 118 };
 119
 120 size_t btr_pool_size(struct btr_pool *btrp);
 121 struct btr_pool *btr_pool_new(const char *name, size_t area_size);
 122 void btr_pool_free(struct btr_pool *btrp);
 123 size_t btr_pool_get_buffer(struct btr_pool *btrp, char **result);
 124 void btr_pool_allocate(struct btr_pool *btrp, size_t size);
 125 void btr_add_output_pool(struct btr_pool *btrp, size_t size,
 126         struct btr_node *btrn);
 127 size_t btr_pool_unused(struct btr_pool *btrp);
 128 void btr_copy(const void *src, size_t n, struct btr_pool *btrp,
 129         struct btr_node *btrn);
 130
 131 struct btr_node *btr_new_node(struct btr_node_description *bnd);
 132 void btr_remove_node(struct btr_node *btrn);
 133 void btr_free_node(struct btr_node *btrn);
 134 void btr_add_output(char *buf, size_t size, struct btr_node *btrn);
 135 bool btr_no_children(struct btr_node *btrn);
 136 size_t btr_bytes_pending(struct btr_node *btrn);
 137 size_t btr_get_input_queue_size(struct btr_node *btrn);
 138 bool btr_no_parent(struct btr_node *btrn);
 139 size_t btr_next_buffer(struct btr_node *btrn, char **bufp);
 140 void btr_consume(struct btr_node *btrn, size_t numbytes);
 141 int btr_exec(struct btr_node *btrn, const char *command, char **value_result);
 142 int btr_exec_up(struct btr_node *btrn, const char *command, char **value_result);
 143 void btr_splice_out_node(struct btr_node *btrn);
 144 void btr_pushdown(struct btr_node *btrn);
 145 void *btr_context(struct btr_node *btrn);
 146 void btr_merge(struct btr_node *btrn, size_t dest_size);
 147 bool btr_eof(struct btr_node *btrn);
 148 void btr_log_tree(struct btr_node *btrn, int loglevel);
 149 int btr_pushdown_one(struct btr_node *btrn);
 150 bool btr_inplace_ok(struct btr_node *btrn);
 151 int btr_node_status(struct btr_node *btrn, size_t min_iqs,
 152                 enum btr_node_type type);
 153 void btr_get_node_start(struct btr_node *btrn, struct timeval *tv);
 154 struct btr_node *btr_search_node(const char *name, struct btr_node *root);