annotate src/fftw-3.3.8/threads/threads.c @ 83:ae30d91d2ffe

Replace these with versions built using an older toolset (so as to avoid ABI compatibilities when linking on Ubuntu 14.04 for packaging purposes)
author Chris Cannam
date Fri, 07 Feb 2020 11:51:13 +0000
parents d0c2a83c1364
children
rev   line source
Chris@82 1 /*
Chris@82 2 * Copyright (c) 2003, 2007-14 Matteo Frigo
Chris@82 3 * Copyright (c) 2003, 2007-14 Massachusetts Institute of Technology
Chris@82 4 *
Chris@82 5 * This program is free software; you can redistribute it and/or modify
Chris@82 6 * it under the terms of the GNU General Public License as published by
Chris@82 7 * the Free Software Foundation; either version 2 of the License, or
Chris@82 8 * (at your option) any later version.
Chris@82 9 *
Chris@82 10 * This program is distributed in the hope that it will be useful,
Chris@82 11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
Chris@82 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
Chris@82 13 * GNU General Public License for more details.
Chris@82 14 *
Chris@82 15 * You should have received a copy of the GNU General Public License
Chris@82 16 * along with this program; if not, write to the Free Software
Chris@82 17 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
Chris@82 18 *
Chris@82 19 */
Chris@82 20
Chris@82 21 /* threads.c: Portable thread spawning for loops, via the X(spawn_loop)
Chris@82 22 function. The first portion of this file is a set of macros to
Chris@82 23 spawn and join threads on various systems. */
Chris@82 24
Chris@82 25 #include "threads/threads.h"
Chris@82 26 #include "api/api.h"
Chris@82 27
Chris@82 28 #if defined(USING_POSIX_THREADS)
Chris@82 29
Chris@82 30 #include <pthread.h>
Chris@82 31
Chris@82 32 #ifdef HAVE_UNISTD_H
Chris@82 33 # include <unistd.h>
Chris@82 34 #endif
Chris@82 35
Chris@82 36 /* imlementation of semaphores and mutexes: */
Chris@82 37 #if (defined(_POSIX_SEMAPHORES) && (_POSIX_SEMAPHORES >= 200112L))
Chris@82 38
Chris@82 39 /* If optional POSIX semaphores are supported, use them to
Chris@82 40 implement both semaphores and mutexes. */
Chris@82 41 # include <semaphore.h>
Chris@82 42 # include <errno.h>
Chris@82 43
Chris@82 44 typedef sem_t os_sem_t;
Chris@82 45
Chris@82 46 static void os_sem_init(os_sem_t *s) { sem_init(s, 0, 0); }
Chris@82 47 static void os_sem_destroy(os_sem_t *s) { sem_destroy(s); }
Chris@82 48
Chris@82 49 static void os_sem_down(os_sem_t *s)
Chris@82 50 {
Chris@82 51 int err;
Chris@82 52 do {
Chris@82 53 err = sem_wait(s);
Chris@82 54 } while (err == -1 && errno == EINTR);
Chris@82 55 CK(err == 0);
Chris@82 56 }
Chris@82 57
Chris@82 58 static void os_sem_up(os_sem_t *s) { sem_post(s); }
Chris@82 59
Chris@82 60 /*
Chris@82 61 The reason why we use sem_t to implement mutexes is that I have
Chris@82 62 seen mysterious hangs with glibc-2.7 and linux-2.6.22 when using
Chris@82 63 pthread_mutex_t, but no hangs with sem_t or with linux >=
Chris@82 64 2.6.24. For lack of better information, sem_t looks like the
Chris@82 65 safest choice.
Chris@82 66 */
Chris@82 67 typedef sem_t os_mutex_t;
Chris@82 68 static void os_mutex_init(os_mutex_t *s) { sem_init(s, 0, 1); }
Chris@82 69 #define os_mutex_destroy os_sem_destroy
Chris@82 70 #define os_mutex_lock os_sem_down
Chris@82 71 #define os_mutex_unlock os_sem_up
Chris@82 72
Chris@82 73 #else
Chris@82 74
Chris@82 75 /* If optional POSIX semaphores are not defined, use pthread
Chris@82 76 mutexes for mutexes, and simulate semaphores with condition
Chris@82 77 variables */
Chris@82 78 typedef pthread_mutex_t os_mutex_t;
Chris@82 79
Chris@82 80 static void os_mutex_init(os_mutex_t *s)
Chris@82 81 {
Chris@82 82 pthread_mutex_init(s, (pthread_mutexattr_t *)0);
Chris@82 83 }
Chris@82 84
Chris@82 85 static void os_mutex_destroy(os_mutex_t *s) { pthread_mutex_destroy(s); }
Chris@82 86 static void os_mutex_lock(os_mutex_t *s) { pthread_mutex_lock(s); }
Chris@82 87 static void os_mutex_unlock(os_mutex_t *s) { pthread_mutex_unlock(s); }
Chris@82 88
Chris@82 89 typedef struct {
Chris@82 90 pthread_mutex_t m;
Chris@82 91 pthread_cond_t c;
Chris@82 92 volatile int x;
Chris@82 93 } os_sem_t;
Chris@82 94
Chris@82 95 static void os_sem_init(os_sem_t *s)
Chris@82 96 {
Chris@82 97 pthread_mutex_init(&s->m, (pthread_mutexattr_t *)0);
Chris@82 98 pthread_cond_init(&s->c, (pthread_condattr_t *)0);
Chris@82 99
Chris@82 100 /* wrap initialization in lock to exploit the release
Chris@82 101 semantics of pthread_mutex_unlock() */
Chris@82 102 pthread_mutex_lock(&s->m);
Chris@82 103 s->x = 0;
Chris@82 104 pthread_mutex_unlock(&s->m);
Chris@82 105 }
Chris@82 106
Chris@82 107 static void os_sem_destroy(os_sem_t *s)
Chris@82 108 {
Chris@82 109 pthread_mutex_destroy(&s->m);
Chris@82 110 pthread_cond_destroy(&s->c);
Chris@82 111 }
Chris@82 112
Chris@82 113 static void os_sem_down(os_sem_t *s)
Chris@82 114 {
Chris@82 115 pthread_mutex_lock(&s->m);
Chris@82 116 while (s->x <= 0)
Chris@82 117 pthread_cond_wait(&s->c, &s->m);
Chris@82 118 --s->x;
Chris@82 119 pthread_mutex_unlock(&s->m);
Chris@82 120 }
Chris@82 121
Chris@82 122 static void os_sem_up(os_sem_t *s)
Chris@82 123 {
Chris@82 124 pthread_mutex_lock(&s->m);
Chris@82 125 ++s->x;
Chris@82 126 pthread_cond_signal(&s->c);
Chris@82 127 pthread_mutex_unlock(&s->m);
Chris@82 128 }
Chris@82 129
Chris@82 130 #endif
Chris@82 131
Chris@82 132 #define FFTW_WORKER void *
Chris@82 133
Chris@82 134 static void os_create_thread(FFTW_WORKER (*worker)(void *arg),
Chris@82 135 void *arg)
Chris@82 136 {
Chris@82 137 pthread_attr_t attr;
Chris@82 138 pthread_t tid;
Chris@82 139
Chris@82 140 pthread_attr_init(&attr);
Chris@82 141 pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM);
Chris@82 142 pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED);
Chris@82 143
Chris@82 144 pthread_create(&tid, &attr, worker, (void *)arg);
Chris@82 145 pthread_attr_destroy(&attr);
Chris@82 146 }
Chris@82 147
Chris@82 148 static void os_destroy_thread(void)
Chris@82 149 {
Chris@82 150 pthread_exit((void *)0);
Chris@82 151 }
Chris@82 152
Chris@82 153 /* support for static mutexes */
Chris@82 154 typedef pthread_mutex_t os_static_mutex_t;
Chris@82 155 #define OS_STATIC_MUTEX_INITIALIZER PTHREAD_MUTEX_INITIALIZER
Chris@82 156 static void os_static_mutex_lock(os_static_mutex_t *s) { pthread_mutex_lock(s); }
Chris@82 157 static void os_static_mutex_unlock(os_static_mutex_t *s) { pthread_mutex_unlock(s); }
Chris@82 158
Chris@82 159 #elif defined(__WIN32__) || defined(_WIN32) || defined(_WINDOWS)
Chris@82 160 /* hack: windef.h defines INT for its own purposes and this causes
Chris@82 161 a conflict with our own INT in ifftw.h. Divert the windows
Chris@82 162 definition into another name unlikely to cause a conflict */
Chris@82 163 #define INT magnus_ab_INTegro_seclorum_nascitur_ordo
Chris@82 164 #include <windows.h>
Chris@82 165 #include <process.h>
Chris@82 166 #include <intrin.h>
Chris@82 167 #undef INT
Chris@82 168
Chris@82 169 typedef HANDLE os_mutex_t;
Chris@82 170
Chris@82 171 static void os_mutex_init(os_mutex_t *s)
Chris@82 172 {
Chris@82 173 *s = CreateMutex(NULL, FALSE, NULL);
Chris@82 174 }
Chris@82 175
Chris@82 176 static void os_mutex_destroy(os_mutex_t *s)
Chris@82 177 {
Chris@82 178 CloseHandle(*s);
Chris@82 179 }
Chris@82 180
Chris@82 181 static void os_mutex_lock(os_mutex_t *s)
Chris@82 182 {
Chris@82 183 WaitForSingleObject(*s, INFINITE);
Chris@82 184 }
Chris@82 185
Chris@82 186 static void os_mutex_unlock(os_mutex_t *s)
Chris@82 187 {
Chris@82 188 ReleaseMutex(*s);
Chris@82 189 }
Chris@82 190
Chris@82 191 typedef HANDLE os_sem_t;
Chris@82 192
Chris@82 193 static void os_sem_init(os_sem_t *s)
Chris@82 194 {
Chris@82 195 *s = CreateSemaphore(NULL, 0, 0x7FFFFFFFL, NULL);
Chris@82 196 }
Chris@82 197
Chris@82 198 static void os_sem_destroy(os_sem_t *s)
Chris@82 199 {
Chris@82 200 CloseHandle(*s);
Chris@82 201 }
Chris@82 202
Chris@82 203 static void os_sem_down(os_sem_t *s)
Chris@82 204 {
Chris@82 205 WaitForSingleObject(*s, INFINITE);
Chris@82 206 }
Chris@82 207
Chris@82 208 static void os_sem_up(os_sem_t *s)
Chris@82 209 {
Chris@82 210 ReleaseSemaphore(*s, 1, NULL);
Chris@82 211 }
Chris@82 212
Chris@82 213 #define FFTW_WORKER unsigned __stdcall
Chris@82 214 typedef unsigned (__stdcall *winthread_start) (void *);
Chris@82 215
Chris@82 216 static void os_create_thread(winthread_start worker,
Chris@82 217 void *arg)
Chris@82 218 {
Chris@82 219 _beginthreadex((void *)NULL, /* security attrib */
Chris@82 220 0, /* stack size */
Chris@82 221 worker, /* start address */
Chris@82 222 arg, /* parameters */
Chris@82 223 0, /* creation flags */
Chris@82 224 (unsigned *)NULL); /* tid */
Chris@82 225 }
Chris@82 226
Chris@82 227 static void os_destroy_thread(void)
Chris@82 228 {
Chris@82 229 _endthreadex(0);
Chris@82 230 }
Chris@82 231
Chris@82 232 /* windows does not have statically-initialized mutexes---fake a
Chris@82 233 spinlock */
Chris@82 234 typedef volatile LONG os_static_mutex_t;
Chris@82 235 #define OS_STATIC_MUTEX_INITIALIZER 0
Chris@82 236 static void os_static_mutex_lock(os_static_mutex_t *s)
Chris@82 237 {
Chris@82 238 while (InterlockedExchange(s, 1) == 1) {
Chris@82 239 YieldProcessor();
Chris@82 240 Sleep(0);
Chris@82 241 }
Chris@82 242 }
Chris@82 243 static void os_static_mutex_unlock(os_static_mutex_t *s)
Chris@82 244 {
Chris@82 245 LONG old = InterlockedExchange(s, 0);
Chris@82 246 A(old == 1);
Chris@82 247 }
Chris@82 248 #else
Chris@82 249 #error "No threading layer defined"
Chris@82 250 #endif
Chris@82 251
Chris@82 252 /************************************************************************/
Chris@82 253
Chris@82 254 /* Main code: */
Chris@82 255 struct worker {
Chris@82 256 os_sem_t ready;
Chris@82 257 os_sem_t done;
Chris@82 258 struct work *w;
Chris@82 259 struct worker *cdr;
Chris@82 260 };
Chris@82 261
Chris@82 262 static struct worker *make_worker(void)
Chris@82 263 {
Chris@82 264 struct worker *q = (struct worker *)MALLOC(sizeof(*q), OTHER);
Chris@82 265 os_sem_init(&q->ready);
Chris@82 266 os_sem_init(&q->done);
Chris@82 267 return q;
Chris@82 268 }
Chris@82 269
Chris@82 270 static void unmake_worker(struct worker *q)
Chris@82 271 {
Chris@82 272 os_sem_destroy(&q->done);
Chris@82 273 os_sem_destroy(&q->ready);
Chris@82 274 X(ifree)(q);
Chris@82 275 }
Chris@82 276
Chris@82 277 struct work {
Chris@82 278 spawn_function proc;
Chris@82 279 spawn_data d;
Chris@82 280 struct worker *q; /* the worker responsible for performing this work */
Chris@82 281 };
Chris@82 282
Chris@82 283 static os_mutex_t queue_lock;
Chris@82 284 static os_sem_t termination_semaphore;
Chris@82 285
Chris@82 286 static struct worker *worker_queue;
Chris@82 287 #define WITH_QUEUE_LOCK(what) \
Chris@82 288 { \
Chris@82 289 os_mutex_lock(&queue_lock); \
Chris@82 290 what; \
Chris@82 291 os_mutex_unlock(&queue_lock); \
Chris@82 292 }
Chris@82 293
Chris@82 294 static FFTW_WORKER worker(void *arg)
Chris@82 295 {
Chris@82 296 struct worker *ego = (struct worker *)arg;
Chris@82 297 struct work *w;
Chris@82 298
Chris@82 299 for (;;) {
Chris@82 300 /* wait until work becomes available */
Chris@82 301 os_sem_down(&ego->ready);
Chris@82 302
Chris@82 303 w = ego->w;
Chris@82 304
Chris@82 305 /* !w->proc ==> terminate worker */
Chris@82 306 if (!w->proc) break;
Chris@82 307
Chris@82 308 /* do the work */
Chris@82 309 w->proc(&w->d);
Chris@82 310
Chris@82 311 /* signal that work is done */
Chris@82 312 os_sem_up(&ego->done);
Chris@82 313 }
Chris@82 314
Chris@82 315 /* termination protocol */
Chris@82 316 os_sem_up(&termination_semaphore);
Chris@82 317
Chris@82 318 os_destroy_thread();
Chris@82 319 /* UNREACHABLE */
Chris@82 320 return 0;
Chris@82 321 }
Chris@82 322
Chris@82 323 static void enqueue(struct worker *q)
Chris@82 324 {
Chris@82 325 WITH_QUEUE_LOCK({
Chris@82 326 q->cdr = worker_queue;
Chris@82 327 worker_queue = q;
Chris@82 328 });
Chris@82 329 }
Chris@82 330
Chris@82 331 static struct worker *dequeue(void)
Chris@82 332 {
Chris@82 333 struct worker *q;
Chris@82 334
Chris@82 335 WITH_QUEUE_LOCK({
Chris@82 336 q = worker_queue;
Chris@82 337 if (q)
Chris@82 338 worker_queue = q->cdr;
Chris@82 339 });
Chris@82 340
Chris@82 341 if (!q) {
Chris@82 342 /* no worker is available. Create one */
Chris@82 343 q = make_worker();
Chris@82 344 os_create_thread(worker, q);
Chris@82 345 }
Chris@82 346
Chris@82 347 return q;
Chris@82 348 }
Chris@82 349
Chris@82 350
Chris@82 351 static void kill_workforce(void)
Chris@82 352 {
Chris@82 353 struct work w;
Chris@82 354
Chris@82 355 w.proc = 0;
Chris@82 356
Chris@82 357 WITH_QUEUE_LOCK({
Chris@82 358 /* tell all workers that they must terminate.
Chris@82 359
Chris@82 360 Because workers enqueue themselves before signaling the
Chris@82 361 completion of the work, all workers belong to the worker queue
Chris@82 362 if we get here. Also, all workers are waiting at
Chris@82 363 os_sem_down(ready), so we can hold the queue lock without
Chris@82 364 deadlocking */
Chris@82 365 while (worker_queue) {
Chris@82 366 struct worker *q = worker_queue;
Chris@82 367 worker_queue = q->cdr;
Chris@82 368 q->w = &w;
Chris@82 369 os_sem_up(&q->ready);
Chris@82 370 os_sem_down(&termination_semaphore);
Chris@82 371 unmake_worker(q);
Chris@82 372 }
Chris@82 373 });
Chris@82 374 }
Chris@82 375
Chris@82 376 static os_static_mutex_t initialization_mutex = OS_STATIC_MUTEX_INITIALIZER;
Chris@82 377
Chris@82 378 int X(ithreads_init)(void)
Chris@82 379 {
Chris@82 380 os_static_mutex_lock(&initialization_mutex); {
Chris@82 381 os_mutex_init(&queue_lock);
Chris@82 382 os_sem_init(&termination_semaphore);
Chris@82 383
Chris@82 384 WITH_QUEUE_LOCK({
Chris@82 385 worker_queue = 0;
Chris@82 386 });
Chris@82 387 } os_static_mutex_unlock(&initialization_mutex);
Chris@82 388
Chris@82 389 return 0; /* no error */
Chris@82 390 }
Chris@82 391
Chris@82 392 /* Distribute a loop from 0 to loopmax-1 over nthreads threads.
Chris@82 393 proc(d) is called to execute a block of iterations from d->min
Chris@82 394 to d->max-1. d->thr_num indicate the number of the thread
Chris@82 395 that is executing proc (from 0 to nthreads-1), and d->data is
Chris@82 396 the same as the data parameter passed to X(spawn_loop).
Chris@82 397
Chris@82 398 This function returns only after all the threads have completed. */
Chris@82 399 void X(spawn_loop)(int loopmax, int nthr, spawn_function proc, void *data)
Chris@82 400 {
Chris@82 401 int block_size;
Chris@82 402 struct work *r;
Chris@82 403 int i;
Chris@82 404
Chris@82 405 A(loopmax >= 0);
Chris@82 406 A(nthr > 0);
Chris@82 407 A(proc);
Chris@82 408
Chris@82 409 if (!loopmax) return;
Chris@82 410
Chris@82 411 /* Choose the block size and number of threads in order to (1)
Chris@82 412 minimize the critical path and (2) use the fewest threads that
Chris@82 413 achieve the same critical path (to minimize overhead).
Chris@82 414 e.g. if loopmax is 5 and nthr is 4, we should use only 3
Chris@82 415 threads with block sizes of 2, 2, and 1. */
Chris@82 416 block_size = (loopmax + nthr - 1) / nthr;
Chris@82 417 nthr = (loopmax + block_size - 1) / block_size;
Chris@82 418
Chris@82 419 STACK_MALLOC(struct work *, r, sizeof(struct work) * nthr);
Chris@82 420
Chris@82 421 /* distribute work: */
Chris@82 422 for (i = 0; i < nthr; ++i) {
Chris@82 423 struct work *w = &r[i];
Chris@82 424 spawn_data *d = &w->d;
Chris@82 425
Chris@82 426 d->max = (d->min = i * block_size) + block_size;
Chris@82 427 if (d->max > loopmax)
Chris@82 428 d->max = loopmax;
Chris@82 429 d->thr_num = i;
Chris@82 430 d->data = data;
Chris@82 431 w->proc = proc;
Chris@82 432
Chris@82 433 if (i == nthr - 1) {
Chris@82 434 /* do the work ourselves */
Chris@82 435 proc(d);
Chris@82 436 } else {
Chris@82 437 /* assign a worker to W */
Chris@82 438 w->q = dequeue();
Chris@82 439
Chris@82 440 /* tell worker w->q to do it */
Chris@82 441 w->q->w = w; /* Dirac could have written this */
Chris@82 442 os_sem_up(&w->q->ready);
Chris@82 443 }
Chris@82 444 }
Chris@82 445
Chris@82 446 for (i = 0; i < nthr - 1; ++i) {
Chris@82 447 struct work *w = &r[i];
Chris@82 448 os_sem_down(&w->q->done);
Chris@82 449 enqueue(w->q);
Chris@82 450 }
Chris@82 451
Chris@82 452 STACK_FREE(r);
Chris@82 453 }
Chris@82 454
Chris@82 455 void X(threads_cleanup)(void)
Chris@82 456 {
Chris@82 457 kill_workforce();
Chris@82 458 os_mutex_destroy(&queue_lock);
Chris@82 459 os_sem_destroy(&termination_semaphore);
Chris@82 460 }
Chris@82 461
Chris@82 462 static os_static_mutex_t install_planner_hooks_mutex = OS_STATIC_MUTEX_INITIALIZER;
Chris@82 463 static os_mutex_t planner_mutex;
Chris@82 464 static int planner_hooks_installed = 0;
Chris@82 465
Chris@82 466 static void lock_planner_mutex(void)
Chris@82 467 {
Chris@82 468 os_mutex_lock(&planner_mutex);
Chris@82 469 }
Chris@82 470
Chris@82 471 static void unlock_planner_mutex(void)
Chris@82 472 {
Chris@82 473 os_mutex_unlock(&planner_mutex);
Chris@82 474 }
Chris@82 475
Chris@82 476 void X(threads_register_planner_hooks)(void)
Chris@82 477 {
Chris@82 478 os_static_mutex_lock(&install_planner_hooks_mutex); {
Chris@82 479 if (!planner_hooks_installed) {
Chris@82 480 os_mutex_init(&planner_mutex);
Chris@82 481 X(set_planner_hooks)(lock_planner_mutex, unlock_planner_mutex);
Chris@82 482 planner_hooks_installed = 1;
Chris@82 483 }
Chris@82 484 } os_static_mutex_unlock(&install_planner_hooks_mutex);
Chris@82 485 }