1 ///////////////////////////////////////////////////////////////////////////////
2 //
3 /// \file outqueue.h
4 /// \brief Output queue handling in multithreaded coding
5 //
6 // Author: Lasse Collin
7 //
8 // This file has been put into the public domain.
9 // You can do whatever you want with this file.
10 //
11 ///////////////////////////////////////////////////////////////////////////////
12
13 #include "common.h"
14
15
16 /// Output buffer for a single thread
17 typedef struct lzma_outbuf_s lzma_outbuf;
18 struct lzma_outbuf_s {
19 /// Pointer to the next buffer. This is used for the cached buffers.
20 /// The worker thread must not modify this.
21 lzma_outbuf *next;
22
23 /// This initialized by lzma_outq_get_buf() and
24 /// is used by lzma_outq_enable_partial_output().
25 /// The worker thread must not modify this.
26 void *worker;
27
28 /// Amount of memory allocated for buf[].
29 /// The worker thread must not modify this.
30 size_t allocated;
31
32 /// Writing position in the worker thread or, in other words, the
33 /// amount of finished data written to buf[] which can be copied out
34 ///
35 /// \note This is read by another thread and thus access
36 /// to this variable needs a mutex.
37 size_t pos;
38
39 /// Decompression: Position in the input buffer in the worker thread
40 /// that matches the output "pos" above. This is used to detect if
41 /// more output might be possible from the worker thread: if it has
42 /// consumed all its input, then more output isn't possible.
43 ///
44 /// \note This is read by another thread and thus access
45 /// to this variable needs a mutex.
46 size_t decoder_in_pos;
47
48 /// True when no more data will be written into this buffer.
49 ///
50 /// \note This is read by another thread and thus access
51 /// to this variable needs a mutex.
52 bool finished;
53
54 /// Return value for lzma_outq_read() when the last byte from
55 /// a finished buffer has been read. Defaults to LZMA_STREAM_END.
56 /// This must *not* be LZMA_OK. The idea is to allow a decoder to
57 /// pass an error code to the main thread, setting the code here
58 /// together with finished = true.
59 lzma_ret finish_ret;
60
61 /// Additional size information. lzma_outq_read() may read these
62 /// when "finished" is true.
63 lzma_vli unpadded_size;
64 lzma_vli uncompressed_size;
65
66 /// Buffer of "allocated" bytes
67 uint8_t buf[];
68 };
69
70
71 typedef struct {
72 /// Linked list of buffers in use. The next output byte will be
73 /// read from the head and buffers for the next thread will be
74 /// appended to the tail. tail->next is always NULL.
75 lzma_outbuf *head;
76 lzma_outbuf *tail;
77
78 /// Number of bytes read from head->buf[] in lzma_outq_read()
79 size_t read_pos;
80
81 /// Linked list of allocated buffers that aren't currently used.
82 /// This way buffers of similar size can be reused and don't
83 /// need to be reallocated every time. For simplicity, all
84 /// cached buffers in the list have the same allocated size.
85 lzma_outbuf *cache;
86
87 /// Total amount of memory allocated for buffers
88 uint64_t mem_allocated;
89
90 /// Amount of memory used by the buffers that are in use in
91 /// the head...tail linked list.
92 uint64_t mem_in_use;
93
94 /// Number of buffers in use in the head...tail list. If and only if
95 /// this is zero, the pointers head and tail above are NULL.
96 uint32_t bufs_in_use;
97
98 /// Number of buffers allocated (in use + cached)
99 uint32_t bufs_allocated;
100
101 /// Maximum allowed number of allocated buffers
102 uint32_t bufs_limit;
103 } lzma_outq;
104
105
106 /**
107 * \brief Calculate the memory usage of an output queue
108 *
109 * \return Approximate memory usage in bytes or UINT64_MAX on error.
110 */
111 extern uint64_t lzma_outq_memusage(uint64_t buf_size_max, uint32_t threads);
112
113
114 /// \brief Initialize an output queue
115 ///
116 /// \param outq Pointer to an output queue. Before calling
117 /// this function the first time, *outq should
118 /// have been zeroed with memzero() so that this
119 /// function knows that there are no previous
120 /// allocations to free.
121 /// \param allocator Pointer to allocator or NULL
122 /// \param threads Number of buffers that may be in use
123 /// concurrently. Note that more than this number
124 /// of buffers may actually get allocated to
125 /// improve performance when buffers finish
126 /// out of order. The actual maximum number of
127 /// allocated buffers is derived from the number
128 /// of threads.
129 ///
130 /// \return - LZMA_OK
131 /// - LZMA_MEM_ERROR
132 ///
133 extern lzma_ret lzma_outq_init(lzma_outq *outq,
134 const lzma_allocator *allocator, uint32_t threads);
135
136
137 /// \brief Free the memory associated with the output queue
138 extern void lzma_outq_end(lzma_outq *outq, const lzma_allocator *allocator);
139
140
141 /// \brief Free all cached buffers that consume memory but aren't in use
142 extern void lzma_outq_clear_cache(
143 lzma_outq *outq, const lzma_allocator *allocator);
144
145
146 /// \brief Like lzma_outq_clear_cache() but might keep one buffer
147 ///
148 /// One buffer is not freed if its size is equal to keep_size.
149 /// This is useful if the caller knows that it will soon need a buffer of
150 /// keep_size bytes. This way it won't be freed and immediately reallocated.
151 extern void lzma_outq_clear_cache2(
152 lzma_outq *outq, const lzma_allocator *allocator,
153 size_t keep_size);
154
155
156 /// \brief Preallocate a new buffer into cache
157 ///
158 /// Splitting the buffer allocation into a separate function makes it
159 /// possible to ensure that way lzma_outq_get_buf() cannot fail.
160 /// If the preallocated buffer isn't actually used (for example, some
161 /// other error occurs), the caller has to do nothing as the buffer will
162 /// be used later or cleared from the cache when not needed.
163 ///
164 /// \return LZMA_OK on success, LZMA_MEM_ERROR if allocation fails
165 ///
166 extern lzma_ret lzma_outq_prealloc_buf(
167 lzma_outq *outq, const lzma_allocator *allocator, size_t size);
168
169
170 /// \brief Get a new buffer
171 ///
172 /// lzma_outq_prealloc_buf() must be used to ensure that there is a buffer
173 /// available before calling lzma_outq_get_buf().
174 ///
175 extern lzma_outbuf *lzma_outq_get_buf(lzma_outq *outq, void *worker);
176
177
178 /// \brief Test if there is data ready to be read
179 ///
180 /// Call to this function must be protected with the same mutex that
181 /// is used to protect lzma_outbuf.finished.
182 ///
183 extern bool lzma_outq_is_readable(const lzma_outq *outq);
184
185
186 /// \brief Read finished data
187 ///
188 /// \param outq Pointer to an output queue
189 /// \param out Beginning of the output buffer
190 /// \param out_pos The next byte will be written to
191 /// out[*out_pos].
192 /// \param out_size Size of the out buffer; the first byte into
193 /// which no data is written to is out[out_size].
194 /// \param unpadded_size Unpadded Size from the Block encoder
195 /// \param uncompressed_size Uncompressed Size from the Block encoder
196 ///
197 /// \return - LZMA: All OK. Either no data was available or the buffer
198 /// being read didn't become empty yet.
199 /// - LZMA_STREAM_END: The buffer being read was finished.
200 /// *unpadded_size and *uncompressed_size were set if they
201 /// were not NULL.
202 ///
203 /// \note This reads lzma_outbuf.finished and .pos variables and thus
204 /// calls to this function need to be protected with a mutex.
205 ///
206 extern lzma_ret lzma_outq_read(lzma_outq *restrict outq,
207 const lzma_allocator *restrict allocator,
208 uint8_t *restrict out, size_t *restrict out_pos,
209 size_t out_size, lzma_vli *restrict unpadded_size,
210 lzma_vli *restrict uncompressed_size);
211
212
213 /// \brief Enable partial output from a worker thread
214 ///
215 /// If the buffer at the head of the output queue isn't finished,
216 /// this will call enable_partial_output on the worker associated with
217 /// that output buffer.
218 ///
219 /// \note This reads a lzma_outbuf.finished variable and thus
220 /// calls to this function need to be protected with a mutex.
221 ///
222 extern void lzma_outq_enable_partial_output(lzma_outq *outq,
223 void (*enable_partial_output)(void *worker));
224
225
226 /// \brief Test if there is at least one buffer free
227 ///
228 /// This must be used before getting a new buffer with lzma_outq_get_buf().
229 ///
230 static inline bool
231 lzma_outq_has_buf(const lzma_outq *outq)
232 {
233 return outq->bufs_in_use < outq->bufs_limit;
234 }
235
236
237 /// \brief Test if the queue is completely empty
238 static inline bool
239 lzma_outq_is_empty(const lzma_outq *outq)
240 {
241 return outq->bufs_in_use == 0;
242 }
243
244
245 /// \brief Get the amount of memory needed for a single lzma_outbuf
246 ///
247 /// \note Caller must check that the argument is significantly less
248 /// than SIZE_MAX to avoid an integer overflow!
249 static inline uint64_t
250 lzma_outq_outbuf_memusage(size_t buf_size)
251 {
252 assert(buf_size <= SIZE_MAX - sizeof(lzma_outbuf));
253 return sizeof(lzma_outbuf) + buf_size;
254 }