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