wimlib.net Git - wimlib/blob - src/compress_parallel.c

   1 /*
   2  * compress_parallel.c
   3  *
   4  * Compress chunks of data (parallel version).
   5  */
   6
   7 /*
   8  * Copyright (C) 2013 Eric Biggers
   9  *
  10  * This file is part of wimlib, a library for working with WIM files.
  11  *
  12  * wimlib is free software; you can redistribute it and/or modify it under the
  13  * terms of the GNU General Public License as published by the Free Software
  14  * Foundation; either version 3 of the License, or (at your option) any later
  15  * version.
  16  *
  17  * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY
  18  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
  19  * A PARTICULAR PURPOSE. See the GNU General Public License for more details.
  20  *
  21  * You should have received a copy of the GNU General Public License along with
  22  * wimlib; if not, see http://www.gnu.org/licenses/.
  23  */
  24
  25 #ifdef HAVE_CONFIG_H
  26 #  include "config.h"
  27 #endif
  28
  29 #include "wimlib/assert.h"
  30 #include "wimlib/compress_chunks.h"
  31 #include "wimlib/error.h"
  32 #include "wimlib/list.h"
  33 #include "wimlib/util.h"
  34 #ifdef __WIN32__
  35 #  include "wimlib/win32.h" /* win32_get_number_of_processors() */
  36 #endif
  37
  38 #include <errno.h>
  39 #include <limits.h>
  40 #include <pthread.h>
  41 #include <stdlib.h>
  42 #include <string.h>
  43 #include <unistd.h>
  44
  45 struct message_queue {
  46         struct list_head list;
  47         pthread_mutex_t lock;
  48         pthread_cond_t msg_avail_cond;
  49         pthread_cond_t space_avail_cond;
  50         bool terminating;
  51 };
  52
  53 struct compressor_thread_data {
  54         pthread_t thread;
  55         struct message_queue *chunks_to_compress_queue;
  56         struct message_queue *compressed_chunks_queue;
  57         int out_ctype;
  58         u32 out_chunk_size;
  59         struct wimlib_lzx_context *comp_ctx;
  60 };
  61
  62 #define MAX_CHUNKS_PER_MSG 2
  63
  64 struct message {
  65         u8 *uncompressed_chunks[MAX_CHUNKS_PER_MSG];
  66         u8 *compressed_chunks[MAX_CHUNKS_PER_MSG];
  67         unsigned uncompressed_chunk_sizes[MAX_CHUNKS_PER_MSG];
  68         unsigned compressed_chunk_sizes[MAX_CHUNKS_PER_MSG];
  69         size_t num_filled_chunks;
  70         size_t num_alloc_chunks;
  71         struct list_head list;
  72         bool complete;
  73         struct list_head submission_list;
  74 };
  75
  76 struct parallel_chunk_compressor {
  77         struct chunk_compressor base;
  78
  79         struct message_queue chunks_to_compress_queue;
  80         struct message_queue compressed_chunks_queue;
  81         struct compressor_thread_data *thread_data;
  82         unsigned num_threads;
  83         unsigned num_started_threads;
  84
  85         struct message *msgs;
  86         size_t num_messages;
  87
  88         struct list_head available_msgs;
  89         struct list_head submitted_msgs;
  90         struct message *next_submit_msg;
  91         struct message *next_ready_msg;
  92         size_t next_chunk_idx;
  93 };
  94
  95 static unsigned
  96 get_default_num_threads(void)
  97 {
  98         long n;
  99 #ifdef __WIN32__
 100         n = win32_get_number_of_processors();
 101 #else
 102         n = sysconf(_SC_NPROCESSORS_ONLN);
 103 #endif
 104         if (n < 1 || n >= UINT_MAX) {
 105                 WARNING("Failed to determine number of processors; assuming 1.");
 106                 return 1;
 107         }
 108         return n;
 109 }
 110
 111 static u64
 112 get_avail_memory(void)
 113 {
 114 #ifdef __WIN32__
 115         u64 phys_bytes = win32_get_avail_memory();
 116         if (phys_bytes == 0)
 117                 goto default_size;
 118         return phys_bytes;
 119 #else
 120         long page_size = sysconf(_SC_PAGESIZE);
 121         long num_pages = sysconf(_SC_PHYS_PAGES);
 122         if (page_size <= 0 || num_pages <= 0)
 123                 goto default_size;
 124         return ((u64)page_size * (u64)num_pages);
 125 #endif
 126
 127 default_size:
 128         WARNING("Failed to determine available memory; assuming 1 GiB");
 129         return 1U << 30;
 130 }
 131
 132 static int
 133 message_queue_init(struct message_queue *q)
 134 {
 135         if (pthread_mutex_init(&q->lock, NULL)) {
 136                 ERROR_WITH_ERRNO("Failed to initialize mutex");
 137                 goto err;
 138         }
 139         if (pthread_cond_init(&q->msg_avail_cond, NULL)) {
 140                 ERROR_WITH_ERRNO("Failed to initialize condition variable");
 141                 goto err_destroy_lock;
 142         }
 143         if (pthread_cond_init(&q->space_avail_cond, NULL)) {
 144                 ERROR_WITH_ERRNO("Failed to initialize condition variable");
 145                 goto err_destroy_msg_avail_cond;
 146         }
 147         INIT_LIST_HEAD(&q->list);
 148         return 0;
 149
 150 err_destroy_msg_avail_cond:
 151         pthread_cond_destroy(&q->msg_avail_cond);
 152 err_destroy_lock:
 153         pthread_mutex_destroy(&q->lock);
 154 err:
 155         return WIMLIB_ERR_NOMEM;
 156 }
 157
 158 static void
 159 message_queue_destroy(struct message_queue *q)
 160 {
 161         if (q->list.next != NULL) {
 162                 pthread_mutex_destroy(&q->lock);
 163                 pthread_cond_destroy(&q->msg_avail_cond);
 164                 pthread_cond_destroy(&q->space_avail_cond);
 165         }
 166 }
 167
 168 static void
 169 message_queue_put(struct message_queue *q, struct message *msg)
 170 {
 171         pthread_mutex_lock(&q->lock);
 172         list_add_tail(&msg->list, &q->list);
 173         pthread_cond_signal(&q->msg_avail_cond);
 174         pthread_mutex_unlock(&q->lock);
 175 }
 176
 177 static struct message *
 178 message_queue_get(struct message_queue *q)
 179 {
 180         struct message *msg;
 181
 182         pthread_mutex_lock(&q->lock);
 183         while (list_empty(&q->list) && !q->terminating)
 184                 pthread_cond_wait(&q->msg_avail_cond, &q->lock);
 185         if (!q->terminating) {
 186                 msg = list_entry(q->list.next, struct message, list);
 187                 list_del(&msg->list);
 188         } else
 189                 msg = NULL;
 190         pthread_mutex_unlock(&q->lock);
 191         return msg;
 192 }
 193
 194 static void
 195 message_queue_terminate(struct message_queue *q)
 196 {
 197         pthread_mutex_lock(&q->lock);
 198         q->terminating = true;
 199         pthread_cond_broadcast(&q->msg_avail_cond);
 200         pthread_mutex_unlock(&q->lock);
 201 }
 202
 203 static int
 204 init_message(struct message *msg, size_t num_chunks, u32 out_chunk_size)
 205 {
 206         msg->num_alloc_chunks = num_chunks;
 207         for (size_t i = 0; i < num_chunks; i++) {
 208                 msg->compressed_chunks[i] = MALLOC(out_chunk_size - 1);
 209                 msg->uncompressed_chunks[i] = MALLOC(out_chunk_size);
 210                 if (msg->compressed_chunks[i] == NULL ||
 211                     msg->uncompressed_chunks[i] == NULL)
 212                         return WIMLIB_ERR_NOMEM;
 213         }
 214         return 0;
 215 }
 216
 217 static void
 218 destroy_message(struct message *msg)
 219 {
 220         for (size_t i = 0; i < msg->num_alloc_chunks; i++) {
 221                 FREE(msg->compressed_chunks[i]);
 222                 FREE(msg->uncompressed_chunks[i]);
 223         }
 224 }
 225
 226 static void
 227 free_messages(struct message *msgs, size_t num_messages)
 228 {
 229         if (msgs) {
 230                 for (size_t i = 0; i < num_messages; i++)
 231                         destroy_message(&msgs[i]);
 232                 FREE(msgs);
 233         }
 234 }
 235
 236 static struct message *
 237 allocate_messages(size_t count, size_t chunks_per_msg, u32 out_chunk_size)
 238 {
 239         struct message *msgs;
 240
 241         msgs = CALLOC(count, sizeof(struct message));
 242         if (msgs == NULL)
 243                 return NULL;
 244         for (size_t i = 0; i < count; i++) {
 245                 if (init_message(&msgs[i], chunks_per_msg, out_chunk_size)) {
 246                         free_messages(msgs, count);
 247                         return NULL;
 248                 }
 249         }
 250         return msgs;
 251 }
 252
 253 static void
 254 compress_chunks(struct message *msg, int out_ctype,
 255                 struct wimlib_lzx_context *comp_ctx)
 256 {
 257
 258         for (size_t i = 0; i < msg->num_filled_chunks; i++) {
 259                 msg->compressed_chunk_sizes[i] =
 260                         compress_chunk(msg->uncompressed_chunks[i],
 261                                        msg->uncompressed_chunk_sizes[i],
 262                                        msg->compressed_chunks[i],
 263                                        out_ctype,
 264                                        comp_ctx);
 265         }
 266 }
 267
 268 static void *
 269 compressor_thread_proc(void *arg)
 270 {
 271         struct compressor_thread_data *params = arg;
 272         struct message *msg;
 273
 274         while ((msg = message_queue_get(params->chunks_to_compress_queue)) != NULL) {
 275                 compress_chunks(msg, params->out_ctype, params->comp_ctx);
 276                 message_queue_put(params->compressed_chunks_queue, msg);
 277         }
 278         return NULL;
 279 }
 280
 281 static void
 282 parallel_chunk_compressor_destroy(struct chunk_compressor *_ctx)
 283 {
 284         struct parallel_chunk_compressor *ctx = (struct parallel_chunk_compressor *)_ctx;
 285         unsigned i;
 286
 287         if (ctx == NULL)
 288                 return;
 289
 290         if (ctx->num_started_threads != 0) {
 291                 DEBUG("Terminating %u compressor threads", ctx->num_started_threads);
 292                 message_queue_terminate(&ctx->chunks_to_compress_queue);
 293
 294                 for (i = 0; i < ctx->num_started_threads; i++)
 295                         pthread_join(ctx->thread_data[i].thread, NULL);
 296         }
 297
 298         message_queue_destroy(&ctx->chunks_to_compress_queue);
 299         message_queue_destroy(&ctx->compressed_chunks_queue);
 300
 301         if (ctx->base.out_ctype == WIMLIB_COMPRESSION_TYPE_LZX &&
 302             ctx->thread_data != NULL)
 303                 for (i = 0; i < ctx->num_threads; i++)
 304                         wimlib_lzx_free_context(ctx->thread_data[i].comp_ctx);
 305
 306         FREE(ctx->thread_data);
 307
 308         free_messages(ctx->msgs, ctx->num_messages);
 309
 310         FREE(ctx);
 311 }
 312
 313 static void
 314 submit_compression_msg(struct parallel_chunk_compressor *ctx)
 315 {
 316         struct message *msg = ctx->next_submit_msg;
 317
 318         msg->complete = false;
 319         list_add_tail(&msg->submission_list, &ctx->submitted_msgs);
 320         message_queue_put(&ctx->chunks_to_compress_queue, msg);
 321         ctx->next_submit_msg = NULL;
 322 }
 323
 324 static bool
 325 parallel_chunk_compressor_submit_chunk(struct chunk_compressor *_ctx,
 326                                        const void *chunk, size_t size)
 327 {
 328         struct parallel_chunk_compressor *ctx = (struct parallel_chunk_compressor *)_ctx;
 329         struct message *msg;
 330
 331         wimlib_assert(size > 0);
 332         wimlib_assert(size <= ctx->base.out_chunk_size);
 333
 334         if (ctx->next_submit_msg) {
 335                 msg = ctx->next_submit_msg;
 336         } else {
 337                 if (list_empty(&ctx->available_msgs))
 338                         return false;
 339
 340                 msg = list_entry(ctx->available_msgs.next, struct message, list);
 341                 list_del(&msg->list);
 342                 ctx->next_submit_msg = msg;
 343                 msg->num_filled_chunks = 0;
 344         }
 345
 346         memcpy(msg->uncompressed_chunks[msg->num_filled_chunks], chunk, size);
 347         msg->uncompressed_chunk_sizes[msg->num_filled_chunks] = size;
 348         if (++msg->num_filled_chunks == msg->num_alloc_chunks)
 349                 submit_compression_msg(ctx);
 350         return true;
 351 }
 352
 353 static bool
 354 parallel_chunk_compressor_get_chunk(struct chunk_compressor *_ctx,
 355                                     const void **cdata_ret, unsigned *csize_ret,
 356                                     unsigned *usize_ret)
 357 {
 358         struct parallel_chunk_compressor *ctx = (struct parallel_chunk_compressor *)_ctx;
 359         struct message *msg;
 360
 361
 362         if (ctx->next_submit_msg)
 363                 submit_compression_msg(ctx);
 364
 365         if (ctx->next_ready_msg) {
 366                 msg = ctx->next_ready_msg;
 367         } else {
 368                 if (list_empty(&ctx->submitted_msgs))
 369                         return false;
 370
 371                 while (!(msg = list_entry(ctx->submitted_msgs.next,
 372                                           struct message,
 373                                           submission_list))->complete)
 374                         message_queue_get(&ctx->compressed_chunks_queue)->complete = true;
 375
 376                 ctx->next_ready_msg = msg;
 377                 ctx->next_chunk_idx = 0;
 378         }
 379
 380         if (msg->compressed_chunk_sizes[ctx->next_chunk_idx]) {
 381                 *cdata_ret = msg->compressed_chunks[ctx->next_chunk_idx];
 382                 *csize_ret = msg->compressed_chunk_sizes[ctx->next_chunk_idx];
 383         } else {
 384                 *cdata_ret = msg->uncompressed_chunks[ctx->next_chunk_idx];
 385                 *csize_ret = msg->uncompressed_chunk_sizes[ctx->next_chunk_idx];
 386         }
 387         *usize_ret = msg->uncompressed_chunk_sizes[ctx->next_chunk_idx];
 388
 389         if (++ctx->next_chunk_idx == msg->num_filled_chunks) {
 390                 list_del(&msg->submission_list);
 391                 list_add_tail(&msg->list, &ctx->available_msgs);
 392                 ctx->next_ready_msg = NULL;
 393         }
 394         return true;
 395 }
 396
 397 int
 398 new_parallel_chunk_compressor(int out_ctype, u32 out_chunk_size,
 399                               unsigned num_threads, u64 max_memory,
 400                               struct chunk_compressor **compressor_ret)
 401 {
 402         u64 approx_mem_required;
 403         size_t chunks_per_msg;
 404         size_t msgs_per_thread;
 405         struct parallel_chunk_compressor *ctx;
 406         unsigned i;
 407         int ret;
 408         unsigned desired_num_threads;
 409
 410         wimlib_assert(out_chunk_size > 0);
 411         wimlib_assert(out_ctype != WIMLIB_COMPRESSION_TYPE_NONE);
 412
 413         if (num_threads == 0)
 414                 num_threads = get_default_num_threads();
 415
 416         if (num_threads == 1) {
 417                 DEBUG("Only 1 thread; Not bothering with "
 418                       "parallel chunk compressor.");
 419                 return -1;
 420         }
 421
 422         if (max_memory == 0)
 423                 max_memory = get_avail_memory();
 424
 425         desired_num_threads = num_threads;
 426
 427         chunks_per_msg = MAX_CHUNKS_PER_MSG;
 428         msgs_per_thread = 2;
 429         for (;;) {
 430                 approx_mem_required =
 431                         (u64)chunks_per_msg *
 432                         (u64)msgs_per_thread *
 433                         (u64)num_threads *
 434                         (u64)out_chunk_size
 435                         + 1000000
 436                         + (out_chunk_size * num_threads * 4);
 437                 if (approx_mem_required <= max_memory)
 438                         break;
 439
 440                 if (chunks_per_msg > 1)
 441                         chunks_per_msg--;
 442                 else if (msgs_per_thread > 1)
 443                         msgs_per_thread--;
 444                 else if (num_threads > 1)
 445                         num_threads--;
 446                 else
 447                         break;
 448         }
 449
 450         if (num_threads < desired_num_threads) {
 451                 WARNING("Wanted to use %u threads, but limiting to %u "
 452                         "to fit in available memory!",
 453                         desired_num_threads, num_threads);
 454         }
 455
 456         if (num_threads == 1) {
 457                 DEBUG("Only 1 thread; Not bothering with "
 458                       "parallel chunk compressor.");
 459                 return -2;
 460         }
 461
 462         ret = WIMLIB_ERR_NOMEM;
 463         ctx = CALLOC(1, sizeof(*ctx));
 464         if (ctx == NULL)
 465                 goto err;
 466
 467         ctx->base.out_ctype = out_ctype;
 468         ctx->base.out_chunk_size = out_chunk_size;
 469         ctx->base.num_threads = num_threads;
 470         ctx->base.destroy = parallel_chunk_compressor_destroy;
 471         ctx->base.submit_chunk = parallel_chunk_compressor_submit_chunk;
 472         ctx->base.get_chunk = parallel_chunk_compressor_get_chunk;
 473
 474         ctx->num_threads = num_threads;
 475
 476         ret = message_queue_init(&ctx->chunks_to_compress_queue);
 477         if (ret)
 478                 goto err;
 479
 480         ret = message_queue_init(&ctx->compressed_chunks_queue);
 481         if (ret)
 482                 goto err;
 483
 484         ret = WIMLIB_ERR_NOMEM;
 485         ctx->thread_data = CALLOC(num_threads, sizeof(ctx->thread_data[0]));
 486         if (ctx->thread_data == NULL)
 487                 goto err;
 488
 489         for (i = 0; i < num_threads; i++) {
 490                 struct compressor_thread_data *dat;
 491
 492                 dat = &ctx->thread_data[i];
 493
 494                 dat->chunks_to_compress_queue = &ctx->chunks_to_compress_queue;
 495                 dat->compressed_chunks_queue = &ctx->compressed_chunks_queue;
 496                 dat->out_ctype = out_ctype;
 497                 dat->out_chunk_size = out_chunk_size;
 498                 if (out_ctype == WIMLIB_COMPRESSION_TYPE_LZX) {
 499                         ret = wimlib_lzx_alloc_context(out_chunk_size, NULL,
 500                                                        &dat->comp_ctx);
 501                         if (ret)
 502                                 goto err;
 503                 }
 504         }
 505
 506         for (ctx->num_started_threads = 0;
 507              ctx->num_started_threads < num_threads;
 508              ctx->num_started_threads++)
 509         {
 510                 DEBUG("pthread_create thread %u of %u",
 511                       ctx->num_started_threads + 1, num_threads);
 512                 ret = pthread_create(&ctx->thread_data[ctx->num_started_threads].thread,
 513                                      NULL,
 514                                      compressor_thread_proc,
 515                                      &ctx->thread_data[ctx->num_started_threads]);
 516                 if (ret) {
 517                         errno = ret;
 518                         ret = WIMLIB_ERR_NOMEM;
 519                         WARNING_WITH_ERRNO("Failed to create compressor thread %u of %u");
 520                         goto err;
 521                 }
 522         }
 523
 524         ret = WIMLIB_ERR_NOMEM;
 525         ctx->num_messages = num_threads * msgs_per_thread;
 526         ctx->msgs = allocate_messages(ctx->num_messages,
 527                                       chunks_per_msg, out_chunk_size);
 528         if (ctx->msgs == NULL)
 529                 goto err;
 530
 531         INIT_LIST_HEAD(&ctx->available_msgs);
 532         for (size_t i = 0; i < ctx->num_messages; i++)
 533                 list_add_tail(&ctx->msgs[i].list, &ctx->available_msgs);
 534
 535         INIT_LIST_HEAD(&ctx->submitted_msgs);
 536
 537         *compressor_ret = &ctx->base;
 538         return 0;
 539
 540 err:
 541         parallel_chunk_compressor_destroy(&ctx->base);
 542         return ret;
 543 }