cannam@167: /*
cannam@167:  * Copyright (c) 2003, 2007-14 Matteo Frigo
cannam@167:  * Copyright (c) 2003, 2007-14 Massachusetts Institute of Technology
cannam@167:  *
cannam@167:  * This program is free software; you can redistribute it and/or modify
cannam@167:  * it under the terms of the GNU General Public License as published by
cannam@167:  * the Free Software Foundation; either version 2 of the License, or
cannam@167:  * (at your option) any later version.
cannam@167:  *
cannam@167:  * This program is distributed in the hope that it will be useful,
cannam@167:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
cannam@167:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
cannam@167:  * GNU General Public License for more details.
cannam@167:  *
cannam@167:  * You should have received a copy of the GNU General Public License
cannam@167:  * along with this program; if not, write to the Free Software
cannam@167:  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
cannam@167:  *
cannam@167:  */
cannam@167: 
cannam@167: /* threads.c: Portable thread spawning for loops, via the X(spawn_loop)
cannam@167:    function.  The first portion of this file is a set of macros to
cannam@167:    spawn and join threads on various systems. */
cannam@167: 
cannam@167: #include "threads/threads.h"
cannam@167: #include "api/api.h"
cannam@167: 
cannam@167: #if defined(USING_POSIX_THREADS)
cannam@167: 
cannam@167: #include <pthread.h>
cannam@167: 
cannam@167: #ifdef HAVE_UNISTD_H
cannam@167: #  include <unistd.h>
cannam@167: #endif
cannam@167: 
cannam@167: /* imlementation of semaphores and mutexes: */
cannam@167: #if (defined(_POSIX_SEMAPHORES) && (_POSIX_SEMAPHORES >= 200112L))
cannam@167: 
cannam@167:    /* If optional POSIX semaphores are supported, use them to
cannam@167:       implement both semaphores and mutexes. */
cannam@167: #  include <semaphore.h>
cannam@167: #  include <errno.h>
cannam@167: 
cannam@167:    typedef sem_t os_sem_t;
cannam@167: 
cannam@167:    static void os_sem_init(os_sem_t *s) { sem_init(s, 0, 0); }
cannam@167:    static void os_sem_destroy(os_sem_t *s) { sem_destroy(s); }
cannam@167: 
cannam@167:    static void os_sem_down(os_sem_t *s)
cannam@167:    {
cannam@167: 	int err;
cannam@167: 	do {
cannam@167: 	     err = sem_wait(s);
cannam@167: 	} while (err == -1 && errno == EINTR);
cannam@167: 	CK(err == 0);
cannam@167:    }
cannam@167: 
cannam@167:    static void os_sem_up(os_sem_t *s) { sem_post(s); }
cannam@167: 
cannam@167:    /*
cannam@167:       The reason why we use sem_t to implement mutexes is that I have
cannam@167:       seen mysterious hangs with glibc-2.7 and linux-2.6.22 when using
cannam@167:       pthread_mutex_t, but no hangs with sem_t or with linux >=
cannam@167:       2.6.24.  For lack of better information, sem_t looks like the
cannam@167:       safest choice.
cannam@167:    */
cannam@167:    typedef sem_t os_mutex_t;
cannam@167:    static void os_mutex_init(os_mutex_t *s) { sem_init(s, 0, 1); }
cannam@167:    #define os_mutex_destroy os_sem_destroy
cannam@167:    #define os_mutex_lock os_sem_down
cannam@167:    #define os_mutex_unlock os_sem_up
cannam@167: 
cannam@167: #else
cannam@167: 
cannam@167:    /* If optional POSIX semaphores are not defined, use pthread
cannam@167:       mutexes for mutexes, and simulate semaphores with condition
cannam@167:       variables */
cannam@167:    typedef pthread_mutex_t os_mutex_t;
cannam@167: 
cannam@167:    static void os_mutex_init(os_mutex_t *s) 
cannam@167:    { 
cannam@167: 	pthread_mutex_init(s, (pthread_mutexattr_t *)0);
cannam@167:    }
cannam@167: 
cannam@167:    static void os_mutex_destroy(os_mutex_t *s) { pthread_mutex_destroy(s); }
cannam@167:    static void os_mutex_lock(os_mutex_t *s) { pthread_mutex_lock(s); }
cannam@167:    static void os_mutex_unlock(os_mutex_t *s) { pthread_mutex_unlock(s); }
cannam@167: 
cannam@167:    typedef struct {
cannam@167: 	pthread_mutex_t m;
cannam@167: 	pthread_cond_t c;
cannam@167: 	volatile int x;
cannam@167:    } os_sem_t; 
cannam@167: 
cannam@167:    static void os_sem_init(os_sem_t *s)
cannam@167:    {
cannam@167: 	pthread_mutex_init(&s->m, (pthread_mutexattr_t *)0);
cannam@167: 	pthread_cond_init(&s->c, (pthread_condattr_t *)0);
cannam@167: 
cannam@167: 	/* wrap initialization in lock to exploit the release
cannam@167: 	   semantics of pthread_mutex_unlock() */
cannam@167: 	pthread_mutex_lock(&s->m);
cannam@167: 	s->x = 0;
cannam@167: 	pthread_mutex_unlock(&s->m);
cannam@167:    }
cannam@167: 
cannam@167:    static void os_sem_destroy(os_sem_t *s)
cannam@167:    {
cannam@167: 	pthread_mutex_destroy(&s->m);
cannam@167: 	pthread_cond_destroy(&s->c);
cannam@167:    }
cannam@167: 
cannam@167:    static void os_sem_down(os_sem_t *s)
cannam@167:    {
cannam@167: 	pthread_mutex_lock(&s->m);
cannam@167: 	while (s->x <= 0) 
cannam@167: 	     pthread_cond_wait(&s->c, &s->m);
cannam@167: 	--s->x;
cannam@167: 	pthread_mutex_unlock(&s->m);
cannam@167:    }
cannam@167: 
cannam@167:    static void os_sem_up(os_sem_t *s)
cannam@167:    {
cannam@167: 	pthread_mutex_lock(&s->m);
cannam@167: 	++s->x;
cannam@167: 	pthread_cond_signal(&s->c);
cannam@167: 	pthread_mutex_unlock(&s->m);
cannam@167:    }
cannam@167: 
cannam@167: #endif
cannam@167: 
cannam@167: #define FFTW_WORKER void *
cannam@167: 
cannam@167: static void os_create_thread(FFTW_WORKER (*worker)(void *arg), 
cannam@167: 			     void *arg)
cannam@167: {
cannam@167:      pthread_attr_t attr;
cannam@167:      pthread_t tid;
cannam@167: 
cannam@167:      pthread_attr_init(&attr);
cannam@167:      pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM); 
cannam@167:      pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED);
cannam@167: 
cannam@167:      pthread_create(&tid, &attr, worker, (void *)arg);
cannam@167:      pthread_attr_destroy(&attr);
cannam@167: }
cannam@167: 
cannam@167: static void os_destroy_thread(void)
cannam@167: {
cannam@167:      pthread_exit((void *)0);
cannam@167: }
cannam@167: 
cannam@167: /* support for static mutexes */
cannam@167: typedef pthread_mutex_t os_static_mutex_t;
cannam@167: #define OS_STATIC_MUTEX_INITIALIZER PTHREAD_MUTEX_INITIALIZER
cannam@167: static void os_static_mutex_lock(os_static_mutex_t *s) { pthread_mutex_lock(s); }
cannam@167: static void os_static_mutex_unlock(os_static_mutex_t *s) { pthread_mutex_unlock(s); }
cannam@167: 
cannam@167: #elif defined(__WIN32__) || defined(_WIN32) || defined(_WINDOWS)
cannam@167: /* hack: windef.h defines INT for its own purposes and this causes
cannam@167:    a conflict with our own INT in ifftw.h.  Divert the windows
cannam@167:    definition into another name unlikely to cause a conflict */
cannam@167: #define INT magnus_ab_INTegro_seclorum_nascitur_ordo
cannam@167: #include <windows.h>
cannam@167: #include <process.h>
cannam@167: #include <intrin.h>
cannam@167: #undef INT
cannam@167: 
cannam@167: typedef HANDLE os_mutex_t;
cannam@167: 
cannam@167: static void os_mutex_init(os_mutex_t *s) 
cannam@167: { 
cannam@167:      *s = CreateMutex(NULL, FALSE, NULL);
cannam@167: }
cannam@167: 
cannam@167: static void os_mutex_destroy(os_mutex_t *s) 
cannam@167: { 
cannam@167:      CloseHandle(*s);
cannam@167: }
cannam@167: 
cannam@167: static void os_mutex_lock(os_mutex_t *s)
cannam@167: { 
cannam@167:      WaitForSingleObject(*s, INFINITE);
cannam@167: }
cannam@167: 
cannam@167: static void os_mutex_unlock(os_mutex_t *s) 
cannam@167: { 
cannam@167:      ReleaseMutex(*s);
cannam@167: }
cannam@167: 
cannam@167: typedef HANDLE os_sem_t;
cannam@167: 
cannam@167: static void os_sem_init(os_sem_t *s) 
cannam@167: {
cannam@167:      *s = CreateSemaphore(NULL, 0, 0x7FFFFFFFL, NULL);
cannam@167: }
cannam@167: 
cannam@167: static void os_sem_destroy(os_sem_t *s) 
cannam@167: { 
cannam@167:      CloseHandle(*s);
cannam@167: }
cannam@167: 
cannam@167: static void os_sem_down(os_sem_t *s) 
cannam@167: { 
cannam@167:      WaitForSingleObject(*s, INFINITE);
cannam@167: }
cannam@167: 
cannam@167: static void os_sem_up(os_sem_t *s) 
cannam@167: {
cannam@167:      ReleaseSemaphore(*s, 1, NULL);
cannam@167: }
cannam@167: 
cannam@167: #define FFTW_WORKER unsigned __stdcall
cannam@167: typedef unsigned (__stdcall *winthread_start) (void *);
cannam@167: 
cannam@167: static void os_create_thread(winthread_start worker,
cannam@167: 			     void *arg)
cannam@167: {
cannam@167:      _beginthreadex((void *)NULL,               /* security attrib */
cannam@167: 		    0,				/* stack size */
cannam@167: 		    worker,                     /* start address */
cannam@167: 		    arg,			/* parameters */
cannam@167: 		    0,				/* creation flags */
cannam@167: 		    (unsigned *)NULL);		/* tid */
cannam@167: }
cannam@167: 
cannam@167: static void os_destroy_thread(void)
cannam@167: {
cannam@167:      _endthreadex(0);
cannam@167: }
cannam@167: 
cannam@167: /* windows does not have statically-initialized mutexes---fake a
cannam@167:    spinlock */
cannam@167: typedef volatile LONG os_static_mutex_t;
cannam@167: #define OS_STATIC_MUTEX_INITIALIZER 0
cannam@167: static void os_static_mutex_lock(os_static_mutex_t *s)
cannam@167: {
cannam@167:      while (InterlockedExchange(s, 1) == 1) {
cannam@167:           YieldProcessor();
cannam@167:           Sleep(0);
cannam@167:      }
cannam@167: }
cannam@167: static void os_static_mutex_unlock(os_static_mutex_t *s)
cannam@167: {
cannam@167:      LONG old = InterlockedExchange(s, 0);
cannam@167:      A(old == 1);
cannam@167: }
cannam@167: #else
cannam@167: #error "No threading layer defined"
cannam@167: #endif
cannam@167: 
cannam@167: /************************************************************************/
cannam@167: 
cannam@167: /* Main code: */
cannam@167: struct worker {
cannam@167:      os_sem_t ready;
cannam@167:      os_sem_t done;
cannam@167:      struct work *w;
cannam@167:      struct worker *cdr;
cannam@167: };
cannam@167: 
cannam@167: static struct worker *make_worker(void)
cannam@167: {
cannam@167:      struct worker *q = (struct worker *)MALLOC(sizeof(*q), OTHER);
cannam@167:      os_sem_init(&q->ready);
cannam@167:      os_sem_init(&q->done);
cannam@167:      return q;
cannam@167: }
cannam@167: 
cannam@167: static void unmake_worker(struct worker *q)
cannam@167: {
cannam@167:      os_sem_destroy(&q->done);
cannam@167:      os_sem_destroy(&q->ready);
cannam@167:      X(ifree)(q);
cannam@167: }
cannam@167: 
cannam@167: struct work {
cannam@167:      spawn_function proc;
cannam@167:      spawn_data d;
cannam@167:      struct worker *q; /* the worker responsible for performing this work */
cannam@167: };
cannam@167: 
cannam@167: static os_mutex_t queue_lock;
cannam@167: static os_sem_t termination_semaphore;
cannam@167: 
cannam@167: static struct worker *worker_queue;
cannam@167: #define WITH_QUEUE_LOCK(what)			\
cannam@167: {						\
cannam@167:      os_mutex_lock(&queue_lock);		\
cannam@167:      what;					\
cannam@167:      os_mutex_unlock(&queue_lock);		\
cannam@167: }
cannam@167: 
cannam@167: static FFTW_WORKER worker(void *arg)
cannam@167: {
cannam@167:      struct worker *ego = (struct worker *)arg;
cannam@167:      struct work *w;
cannam@167: 
cannam@167:      for (;;) {
cannam@167: 	  /* wait until work becomes available */
cannam@167: 	  os_sem_down(&ego->ready);
cannam@167: 
cannam@167: 	  w = ego->w;
cannam@167: 
cannam@167: 	  /* !w->proc ==> terminate worker */
cannam@167: 	  if (!w->proc) break;
cannam@167: 
cannam@167: 	  /* do the work */
cannam@167:           w->proc(&w->d);
cannam@167: 
cannam@167: 	  /* signal that work is done */
cannam@167: 	  os_sem_up(&ego->done);
cannam@167:      }
cannam@167: 
cannam@167:      /* termination protocol */
cannam@167:      os_sem_up(&termination_semaphore);
cannam@167: 
cannam@167:      os_destroy_thread();
cannam@167:      /* UNREACHABLE */
cannam@167:      return 0;
cannam@167: }
cannam@167: 
cannam@167: static void enqueue(struct worker *q)
cannam@167: {
cannam@167:      WITH_QUEUE_LOCK({
cannam@167: 	  q->cdr = worker_queue;
cannam@167: 	  worker_queue = q;
cannam@167:      });
cannam@167: }
cannam@167: 
cannam@167: static struct worker *dequeue(void)
cannam@167: {
cannam@167:      struct worker *q;
cannam@167: 
cannam@167:      WITH_QUEUE_LOCK({
cannam@167: 	  q = worker_queue;
cannam@167: 	  if (q) 
cannam@167: 	       worker_queue = q->cdr;
cannam@167:      });
cannam@167: 
cannam@167:      if (!q) {
cannam@167: 	  /* no worker is available.  Create one */
cannam@167: 	  q = make_worker();
cannam@167: 	  os_create_thread(worker, q);
cannam@167:      }
cannam@167: 
cannam@167:      return q;
cannam@167: }
cannam@167: 
cannam@167: 
cannam@167: static void kill_workforce(void)
cannam@167: {
cannam@167:      struct work w;
cannam@167: 
cannam@167:      w.proc = 0;
cannam@167: 
cannam@167:      WITH_QUEUE_LOCK({
cannam@167: 	  /* tell all workers that they must terminate.  
cannam@167: 
cannam@167: 	     Because workers enqueue themselves before signaling the
cannam@167: 	     completion of the work, all workers belong to the worker queue
cannam@167: 	     if we get here.  Also, all workers are waiting at
cannam@167: 	     os_sem_down(ready), so we can hold the queue lock without
cannam@167: 	     deadlocking */
cannam@167: 	  while (worker_queue) {
cannam@167: 	       struct worker *q = worker_queue;
cannam@167: 	       worker_queue = q->cdr;
cannam@167: 	       q->w = &w;
cannam@167: 	       os_sem_up(&q->ready);
cannam@167: 	       os_sem_down(&termination_semaphore);
cannam@167: 	       unmake_worker(q);
cannam@167: 	  }
cannam@167:      });
cannam@167: }
cannam@167: 
cannam@167: static os_static_mutex_t initialization_mutex = OS_STATIC_MUTEX_INITIALIZER;
cannam@167: 
cannam@167: int X(ithreads_init)(void)
cannam@167: {
cannam@167:      os_static_mutex_lock(&initialization_mutex); {
cannam@167:           os_mutex_init(&queue_lock);
cannam@167:           os_sem_init(&termination_semaphore);
cannam@167: 
cannam@167:           WITH_QUEUE_LOCK({
cannam@167:                worker_queue = 0;
cannam@167:           });
cannam@167:      } os_static_mutex_unlock(&initialization_mutex);
cannam@167: 
cannam@167:      return 0; /* no error */
cannam@167: }
cannam@167: 
cannam@167: /* Distribute a loop from 0 to loopmax-1 over nthreads threads.
cannam@167:    proc(d) is called to execute a block of iterations from d->min
cannam@167:    to d->max-1.  d->thr_num indicate the number of the thread
cannam@167:    that is executing proc (from 0 to nthreads-1), and d->data is
cannam@167:    the same as the data parameter passed to X(spawn_loop).
cannam@167: 
cannam@167:    This function returns only after all the threads have completed. */
cannam@167: void X(spawn_loop)(int loopmax, int nthr, spawn_function proc, void *data)
cannam@167: {
cannam@167:      int block_size;
cannam@167:      struct work *r;
cannam@167:      int i;
cannam@167: 
cannam@167:      A(loopmax >= 0);
cannam@167:      A(nthr > 0);
cannam@167:      A(proc);
cannam@167: 
cannam@167:      if (!loopmax) return;
cannam@167: 
cannam@167:      /* Choose the block size and number of threads in order to (1)
cannam@167:         minimize the critical path and (2) use the fewest threads that
cannam@167:         achieve the same critical path (to minimize overhead).
cannam@167:         e.g. if loopmax is 5 and nthr is 4, we should use only 3
cannam@167:         threads with block sizes of 2, 2, and 1. */
cannam@167:      block_size = (loopmax + nthr - 1) / nthr;
cannam@167:      nthr = (loopmax + block_size - 1) / block_size;
cannam@167: 
cannam@167:      STACK_MALLOC(struct work *, r, sizeof(struct work) * nthr);
cannam@167: 	  
cannam@167:      /* distribute work: */
cannam@167:      for (i = 0; i < nthr; ++i) {
cannam@167: 	  struct work *w = &r[i];
cannam@167: 	  spawn_data *d = &w->d;
cannam@167: 
cannam@167: 	  d->max = (d->min = i * block_size) + block_size;
cannam@167: 	  if (d->max > loopmax)
cannam@167: 	       d->max = loopmax;
cannam@167: 	  d->thr_num = i;
cannam@167: 	  d->data = data;
cannam@167: 	  w->proc = proc;
cannam@167: 	   
cannam@167: 	  if (i == nthr - 1) {
cannam@167: 	       /* do the work ourselves */
cannam@167: 	       proc(d);
cannam@167: 	  } else {
cannam@167: 	       /* assign a worker to W */
cannam@167: 	       w->q = dequeue();
cannam@167: 
cannam@167: 	       /* tell worker w->q to do it */
cannam@167: 	       w->q->w = w; /* Dirac could have written this */
cannam@167: 	       os_sem_up(&w->q->ready);
cannam@167: 	  }
cannam@167:      }
cannam@167: 
cannam@167:      for (i = 0; i < nthr - 1; ++i) { 
cannam@167: 	  struct work *w = &r[i];
cannam@167: 	  os_sem_down(&w->q->done);
cannam@167: 	  enqueue(w->q);
cannam@167:      }
cannam@167: 
cannam@167:      STACK_FREE(r);
cannam@167: }
cannam@167: 
cannam@167: void X(threads_cleanup)(void)
cannam@167: {
cannam@167:      kill_workforce();
cannam@167:      os_mutex_destroy(&queue_lock);
cannam@167:      os_sem_destroy(&termination_semaphore);
cannam@167: }
cannam@167: 
cannam@167: static os_static_mutex_t install_planner_hooks_mutex = OS_STATIC_MUTEX_INITIALIZER;
cannam@167: static os_mutex_t planner_mutex;
cannam@167: static int planner_hooks_installed = 0;
cannam@167: 
cannam@167: static void lock_planner_mutex(void)
cannam@167: {
cannam@167:      os_mutex_lock(&planner_mutex);
cannam@167: }
cannam@167: 
cannam@167: static void unlock_planner_mutex(void)
cannam@167: {
cannam@167:      os_mutex_unlock(&planner_mutex);
cannam@167: }
cannam@167: 
cannam@167: void X(threads_register_planner_hooks)(void)
cannam@167: {
cannam@167:      os_static_mutex_lock(&install_planner_hooks_mutex); {
cannam@167:           if (!planner_hooks_installed) {
cannam@167:                os_mutex_init(&planner_mutex);
cannam@167:                X(set_planner_hooks)(lock_planner_mutex, unlock_planner_mutex);
cannam@167:                planner_hooks_installed = 1;
cannam@167:           }
cannam@167:      } os_static_mutex_unlock(&install_planner_hooks_mutex);
cannam@167: }