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 } 255