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