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