bccb74626d3ccbe4caee8a4e80f2b7e22fc02217
[xscreensaver] / utils / thread_util.c
1 /* -*- mode: c; tab-width: 4; fill-column: 78 -*- */
2 /* vi: set ts=4 tw=78: */
3
4 /*
5 thread_util.c, Copyright (c) 2014 Dave Odell <dmo2118@gmail.com>
6
7 Permission to use, copy, modify, distribute, and sell this software and its
8 documentation for any purpose is hereby granted without fee, provided that
9 the above copyright notice appear in all copies and that both that
10 copyright notice and this permission notice appear in supporting
11 documentation.  No representations are made about the suitability of this
12 software for any purpose.  It is provided "as is" without express or
13 implied warranty.
14 */
15
16 #include "thread_util.h"
17
18 #include "aligned_malloc.h"
19 #include "resources.h"
20
21 #if HAVE_CONFIG_H
22 #       include "config.h"
23 #endif
24
25 #include <assert.h>
26 #include <errno.h>
27 #include <limits.h>
28 #include <stdlib.h>
29 #include <stdio.h> /* Only used by thread_memory_alignment(). */
30 #include <string.h>
31
32 #if HAVE_ALLOCA_H
33 #       include <alloca.h>
34 #endif
35
36 #if HAVE_UNISTD_H
37 #       include <unistd.h>
38 #endif
39
40 #if defined __MACH__ && defined __APPLE__ /* OS X, iOS */
41 #       include <sys/sysctl.h>
42 #       include <inttypes.h>
43 #endif
44
45 #define IS_POWER_OF_2(x) ((x) > 0 && !((x) & ((x) - 1)))
46
47 /*
48    arraysize(a). Also known as countof(x), XtNumber(x), NELEMS(x), LEN(x),
49    NUMOF(x), ARRAY_SIZE(x), etc., since the fine folks behind C never got
50    around to including this incredibly useful macro in the standard library,
51    which is where it belongs.
52
53    Much of the code here assumes that multiple processors in a system all use
54    the same cache line size...which might be wrong on occasion.
55 */
56
57 #define arraysize(a) (sizeof(a) / sizeof(*(a)))
58 #define arrayend(a) ((a) + arraysize(a))
59
60 /*
61 These numbers are from:
62 - Linux: arch/(arch name)/include/asm/cache.h, note
63   L1_CACHE_BYTES/L1_CACHE_SHIFT/SMP_CACHE_BYTES.
64 - FreeBSD: sys/(sys name)/include/param.h, note
65   CACHE_LINE_SHIFT/CACHE_LINE_SIZE.
66
67 Preprocessor symbols come from:
68 - TARGET_CPU_CPP_BUILTINS() in the GNU C preprocessor
69   <http://code.ohloh.net/?s=%22TARGET_CPU_CPP_BUILTINS%22&fp=304413>
70 - http://predef.sourceforge.net/
71 */
72
73 /*
74 Several architectures need preprocessor symbols.
75
76 Qualcomm Hexagon: 1 << 5
77 Imagination Technologies META: 1 << 6
78 OpenRISC: 16 (Linux has the cache line size as a todo.)
79 Unicore: 1 << 5
80 */
81
82 #if HAVE_PTHREAD
83
84 #       if !HAVE_UNISTD_H
85 #               error unistd.h must be present whenever pthread.h is.
86 #       endif
87
88 #       if defined __MACH__ && defined __APPLE__ /* OS X, iOS */
89 #               include <TargetConditionals.h> /* For TARGET_OS_IPHONE. */
90 #               ifdef TARGET_OS_IPHONE
91 #                       define _CACHE_LINE_SIZE 64
92 #               endif
93 #       endif
94
95 #       if defined __FreeBSD__ && !defined _CACHE_LINE_SIZE
96 #               include <machine/param.h>
97 #               ifdef CACHE_LINE_SIZE
98 #                       define _CACHE_LINE_SIZE CACHE_LINE_SIZE
99 #               endif
100 #       endif
101
102 #       if !defined _CACHE_LINE_SIZE
103 #               if defined __alpha || defined __alpha__
104 /* DEC Alpha */
105 #                       define _CACHE_LINE_SIZE 64 /* EV6 and above. EV4 and EV5 use 32 bytes. */
106 #               elif defined __arm__
107 /* ARM architecture */
108 #                       define _CACHE_LINE_SIZE (1 << 6)
109 #               elif defined __AVR || defined __AVR__
110 /* Atmel AVR32 */
111 #                       define _CACHE_LINE_SIZE (1 << 5)
112 #               elif defined __bfin || defined __BFIN__
113 /* Analog Devices Blackfin */
114 #                       define _CACHE_LINE_SIZE (1 << 5)
115 #               elif defined _TMS320C6X || defined __TMS320C6X__
116 /* Texas Instruments TMS320C6x */
117 #                       define _CACHE_LINE_SIZE (1 << 7) /* From L2. L1 data cache line is 1 << 6. */
118 #               elif defined __cris
119 /* Axis Communications ETRAX CRIS */
120 #                       define _CACHE_LINE_SIZE 32
121 #               elif defined __ia64__ || defined _IA64
122 /* Intel Itanium */
123 #                       define _CACHE_LINE_SIZE (1 << 7)
124 #               elif defined __M32R__ || defined __m32r__
125 /* Mitsubishi/Renesas M32R */
126 #                       define _CACHE_LINE_SIZE (1 << 4)
127 #               elif defined __m68k__ || defined M68000 || defined __MC68K__
128 /* Motorola 68000 */
129 #                       define _CACHE_LINE_SIZE (1 << 4)
130 #               elif defined __MICROBLAZE__ || defined __microblaze__
131 /* Xilinx MicroBlaze */
132 #                       define _CACHE_LINE_SIZE (1 << 5)
133 #               elif defined __mips__ || defined __mips || defined __MIPS__
134 /* MIPS */
135 #                       define _CACHE_LINE_SIZE (1 << 6)
136 #               elif defined __mn10300__ || defined __MN10300__
137 /* Matsushita/Panasonic MN103 */
138 #                       define _CACHE_LINE_SIZE 32 /* MN103E010 has 16 bytes. */
139 #               elif defined __hppa || defined __hppa__
140 /* Hewlett-Packard PA-RISC */
141 #                       define _CACHE_LINE_SIZE 64 /* PA-RISC 2.0 uses 64 bytes, PA-RISC 1.1 uses 32. */
142 #               elif defined __powerpc || defined _ARCH_PPC
143 /* Power Architecture (a.k.a. PowerPC) */
144 #                       define _CACHE_LINE_SIZE (1 << 7) /* Linux has a list of PPC models with associated L1_CACHE_SHIFT values. */
145 #               elif defined __s390__ || defined __370__ || defined __zarch__ || defined __SYSC_ZARCH__
146 /* IBM System/390 */
147 #                       define _CACHE_LINE_SIZE 256
148 #               elif defined SUNPLUS || defined __SCORE__ || defined __score__
149 /* Sunplus S+core */
150 #                       define _CACHE_LINE_SIZE (1 << 4)
151 #               elif defined __sh__
152 /* Hitachi SuperH */
153 #                       define _CACHE_LINE_SIZE (1 << 5) /* SH3 and earlier used 1 << 4. */
154 #               elif defined __sparc__ || defined __sparc
155 /* SPARC */
156 #                       define _CACHE_LINE_SIZE (1 << 7) /* Linux and FreeBSD disagree as to what this should be. */
157 #               elif defined __tile__
158 /* Tilera TILE series */
159 #                       define _CACHE_LINE_SIZE (1 << 6) /* TILEPro uses different sizes for L1 and L2. */
160 #               elif defined __i386 || defined __x86_64
161 /* x86(-64) */
162 #                       define _CACHE_LINE_SIZE (1 << 7)
163 #               elif defined __xtensa__ || defined __XTENSA__
164 /* Cadence Design Systems/Tensilica Xtensa */
165 #                       define _CACHE_LINE_SIZE (1 << 5) /* 1 << 4 on some models. */
166 #               endif
167 #       endif /* !defined _CACHE_LINE_SIZE */
168
169 #       if defined __NetBSD__ && !defined _CACHE_LINE_SIZE
170 /*
171 NetBSD defines COHERENCY_UNIT to be 32 on MIPS, and 64 for all other platforms -- which is wrong. Still, this is what the kernel
172 uses; if this value didn't work, the system wouldn't run.
173 */
174 #               include <sys/param.h>
175 #                       ifdef COHERENCY_UNIT
176 #                       define _CACHE_LINE_SIZE COHERENCY_UNIT
177 #               endif
178 #       endif
179
180 #       ifndef _CACHE_LINE_SIZE
181 #               define _CACHE_LINE_SIZE 256 /* Fallback cache line size. */
182 #       endif
183
184 static unsigned _get_cache_line_size(void)
185 {
186         /*
187         The general idea:
188         - Try to get the actual cache line size from the operating system.
189           - In the interest of keeping things simple, this only checks with
190         glibc and OS X.
191             - A few other methods that could be added:
192               - Query x86 CPUs directly with the CPUID instruction.
193               - Query various ELF systems through the auxillary vector.
194             (Power, Alpha, SuperH)
195               - Query Linux through
196             /sys/devices/system/cpu/cpu?/cache/index?/coherency_line_size
197             (x86 only, AFAIK)
198               - Query Linux through cache_alignment in /proc/cpuinfo
199               - Query Solaris through PICL.
200         - If that fails, return a value appropriate for the current CPU
201       architecture.
202         - Otherwise, return a sufficiently large number.
203         */
204
205         /*
206         sysconf(3) is not a syscall, it's a glibc call that, for cache line sizes,
207         uses CPUID on x86 and returns 0 on other platforms. If it were to work on
208         most other platforms, it would have to get cache information from the
209         kernel, since that information is usually made available by the processor
210         only in privileged mode.
211         https://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/unix/sysv/linux/i386/sysconf.c;hb=HEAD
212         */
213
214         /* uClibc, newlib, dietlibc, musl, Bionic do not have this. */
215
216 #       if HAVE_UNISTD_H && ( \
217         defined _SC_LEVEL1_DCACHE_LINESIZE || \
218         defined _SC_LEVEL2_CACHE_LINESIZE || \
219         defined _SC_LEVEL3_CACHE_LINESIZE || \
220         defined _SC_LEVEL4_CACHE_LINESIZE)
221         {
222                 static const int names[] =
223                 {
224 #               ifdef _SC_LEVEL1_DCACHE_LINESIZE
225                         _SC_LEVEL1_DCACHE_LINESIZE,
226 #               endif
227 #               ifdef _SC_LEVEL2_CACHE_LINESIZE
228                         _SC_LEVEL2_CACHE_LINESIZE,
229 #               endif
230 #               ifdef _SC_LEVEL3_CACHE_LINESIZE
231                         _SC_LEVEL3_CACHE_LINESIZE,
232 #               endif
233 #               ifdef  _SC_LEVEL4_CACHE_LINESIZE
234                         _SC_LEVEL4_CACHE_LINESIZE
235 #               endif
236                 };
237
238                 const int *name;
239                 long result = 0;
240
241                 for(name = names; name != arrayend(names); ++name)
242                 {
243                         long sysconf_result = sysconf(*name); /* Can return -1 or 0 on
244                                                      failure. */
245
246                         if(sysconf_result > result)
247                                 result = sysconf_result;
248                 }
249
250                 if(result)
251                         return result;
252
253                 /* Currently, this fails for every platform that isn't x86. Perhaps
254            future versions will support other processors? */
255         }
256 #       endif
257
258 #       if defined __MACH__ && defined __APPLE__
259         {
260                 uint32_t result; /* sysctl.h says that hw.cachelinesize is a
261                             CTLTYPE_INT. */
262                 size_t size = sizeof(result);
263                 static const int name[] = {CTL_HW, HW_CACHELINE};
264
265                 if(!sysctl((int *)name, 2, &result, &size, NULL, 0)) /* (int *) is for OS X. */
266                 {
267                         assert(size == sizeof(result));
268                         return result;
269                 };
270         }
271 #       endif
272
273         /* Guess based on the CPU type. */
274         return _CACHE_LINE_SIZE;
275 }
276
277 const pthread_mutex_t mutex_initializer =
278 #       if defined _GNU_SOURCE && !defined NDEBUG
279         PTHREAD_ERRORCHECK_MUTEX_INITIALIZER_NP
280 #       else
281         PTHREAD_MUTEX_INITIALIZER
282 #       endif
283         ;
284
285 const pthread_cond_t cond_initializer = PTHREAD_COND_INITIALIZER;
286
287 static int _has_pthread = 0; /* Initialize when needed. */
288 static int _cache_line_size = sizeof(void *);
289
290 /* This is actually the init function for various things in here. */
291 int threads_available(Display *dpy)
292 {
293 /*      This is maybe not thread-safe, but: this should -- and generally will --
294         be called before the program launches its second thread. */
295
296         if(!_has_pthread)
297         {
298 #       if _POSIX_THREADS
299                 _has_pthread = _POSIX_THREADS;
300 #       else
301                 _has_pthread = sysconf(_SC_THREADS);
302 #       endif
303
304                 if(_has_pthread >= 0)
305                 {
306                         if(get_boolean_resource(dpy, "useThreads", "Boolean"))
307                         {
308                                 _cache_line_size = _get_cache_line_size();
309                                 assert(_cache_line_size >= sizeof(void *));
310                                 assert(IS_POWER_OF_2(_cache_line_size));
311                         }
312                         else
313                         {
314                                 _has_pthread = -1;
315                         }
316                 }
317         }
318
319         return _has_pthread;
320 }
321
322 #endif /* HAVE_PTHREAD */
323
324 /*
325    hardware_concurrency() -
326
327    Various platforms offer various statistics that look like they should be
328    useful: sysconf(_SC_NPROCESSORS_ONLN) (i.e. the number of 'online'
329    processors) in particular is available on many Unixes, and is frequently
330    used for functions like hardware_concurrency(). But 'online' is somewhat
331    ambiguous; it can mean:
332
333   1. The number of CPU cores that are not (temporarily) asleep. (e.g. Android
334      can sometimes put cores to sleep if they aren't being used, and this is
335      reflected in _SC_NPROCESSORS_ONLN.)
336
337   2. The maximum number of CPU cores that can be provided to this application,
338      as currently set by the system administrator.  (2) is the one that
339      hardware_concurrency() ultimately needs.
340 */
341
342 /*
343    Shamelessly plagarized from Boost.Thread and Stack Overflow
344    <http://stackoverflow.com/q/150355>.  GNU libstdc++ has some of this too,
345    see thread::hardware_concurrency() in thread.cc.
346    http://gcc.gnu.org/viewcvs/gcc/trunk/libstdc%2B%2B-v3/src/c%2B%2B11/thread.cc?view=markup
347
348    This might not work right on less common systems for various reasons.
349 */
350
351 #if HAVE_PTHREAD
352 #       if defined __APPLE__ && defined __MACH__ || \
353                 defined __FreeBSD__ || \
354                 defined __OpenBSD__ || \
355                 defined __NetBSD__ || \
356                 defined __DragonFly__ || \
357                 defined __minix
358
359 /*
360    BSD Unixes use sysctl(3) for this.
361    Some BSDs also support sysconf(3) for this, but in each case this was added
362    after sysctl(3).
363    Linux: sysctl is present, but strongly deprecated.
364    Minix uses the NetBSD userspace, so it has both this and sysconf(3).
365    QNX: sysctl is present for kern.* and net.*, but it doesn't say anything
366    about hw.*
367 */
368
369 /* __APPLE__ without __MACH__ is OS 9 or earlier. __APPLE__ with __MACH__ is OS X. */
370
371 /*
372 The usual thing to do here is for sysctl(3) to call __sysctl(2).
373   http://cvsweb.netbsd.org/bsdweb.cgi/src/lib/libc/gen/sysctl.c?only_with_tag=HEAD
374   http://svnweb.freebsd.org/base/head/lib/libc/gen/sysctl.c?view=markup
375 */
376
377 /*
378    OS X: Xcode Instruments (as of Xcode 4; Apple likes to move things like
379    this around) can disable CPUs as a debugging tool.
380    Instruments -> Preferences... (Command-,) -> General -> Active Processor Cores
381    FreeBSD, OpenBSD: It doesn't look like CPUs can be disabled.
382    NetBSD: CPUs can be disabled manually through cpuctl(8).
383 */
384
385 #               include <stddef.h>
386
387 /* FreeBSD: sys/sysctl.h needs sys/types.h, but the one doesn't bring the
388    other in automatically. */
389 #               include <sys/types.h>
390 #               include <sys/sysctl.h>
391
392 static unsigned _hardware_concurrency(void)
393 {
394         int count;
395         size_t size = sizeof(count);
396
397 #               if defined __APPLE__ && defined __MACH__
398         /* Apple sez: sysctl("hw.logicalcpu") is affected by the "current power
399        management mode", so use hw.logicalcpu_max. */
400         /* https://developer.apple.com/library/mac/#documentation/Darwin/Reference/ManPages/man3/sysctl.3.html */
401         if(!sysctlbyname("hw.logicalcpu_max", &count, &size, NULL, 0)) /* Preferred on more recent Darwin. */
402         {
403                 assert(size == sizeof(count));
404                 return count;
405         }
406 #               endif
407
408 #               if defined HW_NCPUONLINE
409         /* NetBSD has this. */
410         {
411                 static const int name[] = {CTL_HW, HW_NCPUONLINE};
412                 if(!sysctl(name, 2, &count, &size, NULL, 0))
413                 {
414                         assert(size == sizeof(count));
415                         return count;
416                 }
417         }
418 #               endif
419
420         {
421                 static const int name[] = {CTL_HW, HW_NCPU};
422                 if(!sysctl((int *)name, 2, &count, &size, NULL, 0)) /* (int *) is for OS X. */
423                 {
424                         assert(size == sizeof(count));
425                         return count;
426                 }
427         }
428
429         return 1;
430 }
431
432 #       elif HAVE_UNISTD_H && defined _SC_NPROCESSORS_ONLN
433
434 /*
435 Supported by:
436 Linux 2.0 was the first version to provide SMP support via clone(2).
437   (e)glibc on Linux provides this, which in turn uses get_nprocs().
438   get_nprocs in turn uses /sys/devices/system/cpu/online, /proc/stat, or /proc/cpuinfo, whichever's available.
439   https://sourceware.org/git/?p=glibc.git;a=blob;f=posix/sysconf.c;hb=HEAD
440   https://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/unix/sysv/linux/getsysstats.c;hb=HEAD
441   Linux usually isn't configured to auto-enable/disable cores.
442 SunOS (Solaris), sometime between 4.1.3 and 5.5.1.
443   This includes all open source derivatives of 5.10. (Illumos, OpenIndiana)
444   sysconf(_SC_NPROCESSORS_ONLN) call _sysconfig(2).
445   Not sure if CPU power management (enabled by default, see cpupm and
446   cpu_deep_idle in power.conf(4)) affects this.
447   psradm(1M) can bring up/down CPU cores, which affects
448   sysconf(_SC_NPROCESSORS_ONLN).
449   http://src.illumos.org/source/xref/illumos-gate/usr/src/lib/libc/port/gen/sysconf.c
450   Minix 3.2, at the latest. (This is the first version to support SMP.)
451   AIX 7.1, probably earlier.
452
453 Also:
454 Mac OS X apparently has this on 10.5+.
455 FreeBSD 5.0, NetBSD 5.0 also have this. They both call sysctl(3).
456   http://svnweb.freebsd.org/base/head/lib/libc/gen/sysconf.c?view=markup
457   http://cvsweb.netbsd.org/bsdweb.cgi/src/lib/libc/gen/sysconf.c?only_with_tag=HEAD
458
459 QNX has sysconf(3), but it doesn't have _SC_NPROCESSORS_*.
460 */
461
462 static unsigned _hardware_concurrency(void)
463 {
464         long count = sysconf(_SC_NPROCESSORS_ONLN);
465         return count > 0 ? count : 1;
466 }
467
468 #       else
469
470 static unsigned _hardware_concurrency(void)
471 {
472         return 1; /* Fallback for unknown systems. */
473 }
474
475 #       endif
476 #endif
477
478 unsigned hardware_concurrency(Display *dpy)
479 {
480 #if HAVE_PTHREAD
481         if(threads_available(dpy) >= 0)
482                 return _hardware_concurrency();
483 #endif
484         return 1;
485 }
486
487 /* thread_memory_alignment() - */
488
489 unsigned thread_memory_alignment(Display *dpy)
490 {
491         (void)threads_available(dpy);
492 #if HAVE_PTHREAD
493         return _cache_line_size;
494 #else
495         return sizeof(void *);
496 #endif
497 }
498
499 /* Thread pool - */
500
501 static unsigned _threadpool_count_serial(struct threadpool *self)
502 {
503 #if HAVE_PTHREAD
504         assert(_has_pthread);
505         if(_has_pthread >= 0)
506                 return self->count ? 1 : 0;
507 #endif
508         return self->count;
509 }
510
511 static void _serial_destroy(struct threadpool *self)
512 {
513         void *thread = self->serial_threads;
514         unsigned i, count = _threadpool_count_serial(self);
515
516         for(i = 0; i != count; ++i)
517         {
518                 self->thread_destroy(thread);
519                 thread = (char *)thread + self->thread_size;
520         }
521
522         free(self->serial_threads);
523 }
524
525 #if HAVE_PTHREAD
526
527 static void _parallel_abort(struct threadpool *self)
528 {
529         assert(self->count > 1);
530         self->count = self->parallel_unfinished + 1 /* The '+ 1' should technically be _threadpool_count_serial(self). */;
531         PTHREAD_VERIFY(pthread_cond_broadcast(&self->cond));
532 }
533
534 struct _parallel_startup_type
535 {
536         struct threadpool *parent;
537         int (*thread_create)(void *self, struct threadpool *pool, unsigned id);
538         int last_errno;
539 };
540
541 static unsigned _threadpool_count_parallel(struct threadpool *self)
542 {
543         assert(_has_pthread);
544         assert(self->count >= 1);
545         return self->count - 1 /* The '- 1' should technically be _threadpool_count_serial(self). */;
546 }
547
548 static void *_start_routine(void *startup_raw);
549
550 /* Tricky lock sequence: _add_next_thread unlocks on error. */
551 static void _add_next_thread(struct _parallel_startup_type *self)
552 {
553         assert(!self->last_errno);
554
555         if(self->parent->parallel_unfinished == _threadpool_count_parallel(self->parent))
556         {
557                 PTHREAD_VERIFY(pthread_cond_broadcast(&self->parent->cond));
558         }
559         else
560         {
561                 pthread_t *thread = self->parent->parallel_threads + self->parent->parallel_unfinished;
562                 self->last_errno = pthread_create(thread, NULL, _start_routine, self);
563                 if(self->last_errno)
564                         _parallel_abort(self->parent);
565         }
566 }
567
568 static void *_thread_free_and_unlock(struct threadpool *self, void *thread)
569 {
570         PTHREAD_VERIFY(pthread_mutex_unlock(&self->mutex));
571 #       if !HAVE_ALLOCA
572         thread_free(thread);
573 #       endif
574         return NULL;
575 }
576
577 static void *_thread_destroy_and_unlock(struct threadpool *self, void *thread)
578 {
579         self->thread_destroy(thread);
580         return _thread_free_and_unlock(self, thread);
581 }
582
583 /* At one point, one of the threads refused to destroy itself at the end. Why?! And why won't it happen again? */
584
585 static void *_start_routine(void *startup_raw)
586 {
587         struct _parallel_startup_type *startup = (struct _parallel_startup_type *)startup_raw;
588
589         struct threadpool *parent = startup->parent;
590
591         void *thread;
592
593         PTHREAD_VERIFY(pthread_mutex_lock(&parent->mutex));
594         ++parent->parallel_unfinished;
595
596 #       if HAVE_ALLOCA
597 /*      Ideally, the thread object goes on the thread's stack. This guarantees no false sharing with other threads, and in a NUMA
598         configuration, ensures that the thread object is using memory from the right node. */
599         thread = alloca(parent->thread_size);
600 #       else
601         startup->last_errno = thread_malloc(&thread, NULL, parent->thread_size);
602         if(startup->last_errno)
603         {
604                 _parallel_abort(parent);
605                 PTHREAD_VERIFY(pthread_mutex_unlock(&parent->mutex));
606                 return NULL;
607         }
608 #       endif
609
610 /*      Setting thread affinity for threads running in lock-step can cause delays
611         and jumpiness.  Ideally, there would be some way to recommend (but not
612         require) that a thread run on a certain core/set of cores. */
613
614 /*      Neither Linux nor libnuma seem to support the concept of a preferred/ideal
615         CPU for a thread/process. */
616
617 /*      Untested. */
618 /*      {
619                 cpu_set_t cpu_set;
620                 CPU_ZERO(&cpu_set);
621                 CPU_SET(&cpu_set, &parent._threads_unfinished);
622                 pthread_setaffinity_np(pthread_self(), sizeof(cpu_set_t), &cpu_set);
623         } */
624
625         startup->last_errno = startup->thread_create(thread, parent, parent->parallel_unfinished);
626         if(startup->last_errno)
627         {
628                 _parallel_abort(parent);
629                 return _thread_free_and_unlock(parent, thread); /* Tail calls make everything better. */
630         }
631
632         assert(!startup->last_errno);
633         _add_next_thread(startup); /* Calls _parallel_abort() on failure. */
634         if(startup->last_errno)
635                 return _thread_destroy_and_unlock(parent, thread);
636
637         for(;;)
638         {
639                 for(;;)
640                 {
641                         /*
642                         This must come before the '.threads' check, otherwise if
643                         threadpool_destroy is called immediately after a run starts, then
644                         it's possible that not all threads would be launched for the final
645                         run. This can cause deadlock in conjunction with things like
646                         barriers.
647                         */
648                         if(parent->parallel_pending)
649                                 break; /* Start a run. */
650
651                         if(!parent->parallel_threads)
652                                 return _thread_destroy_and_unlock(parent, thread); /* Threads are shutting down. */
653
654                         PTHREAD_VERIFY(pthread_cond_wait(&parent->cond, &parent->mutex));
655                 }
656
657                 --parent->parallel_pending;
658                 if(!parent->parallel_pending)
659                         PTHREAD_VERIFY(pthread_cond_broadcast(&parent->cond));
660                         /* All threads have started processing, other threads can finish. */
661
662                 PTHREAD_VERIFY(pthread_mutex_unlock(&parent->mutex));
663
664                 parent->thread_run(thread);
665
666                 PTHREAD_VERIFY(pthread_mutex_lock(&parent->mutex));
667 #       if 0
668                 if(!parent->parallel_threads) /* I don't think this is necessary anymore. */
669                         break;
670 #       endif
671                 /* Don't loop around until all other threads have begun processing. */
672
673                 /* I suspect it doesn't matter whether this comes before or after the threads_unfinished check. */
674                 while(parent->parallel_pending)
675                         PTHREAD_VERIFY(pthread_cond_wait(&parent->cond, &parent->mutex));
676
677                 --parent->parallel_unfinished;
678                 if(!parent->parallel_unfinished)
679                         PTHREAD_VERIFY(pthread_cond_broadcast(&parent->cond)); /* All threads done for now. */
680         }
681
682         /* return _thread_destroy_and_unlock(parent, thread); */
683 }
684
685 static void _unlock_and_destroy(struct threadpool *self)
686 {
687         pthread_t *threads;
688
689         threads = self->parallel_threads;
690         self->parallel_threads = NULL;
691
692         if(threads)
693                 PTHREAD_VERIFY(pthread_cond_broadcast(&self->cond));
694
695         PTHREAD_VERIFY(pthread_mutex_unlock(&self->mutex));
696
697         if(!threads)
698                 return;
699
700         {
701                 unsigned i, count = _threadpool_count_parallel(self);
702                 for(i = 0; i != count; ++i)
703                         PTHREAD_VERIFY(pthread_join(threads[i], NULL));
704         }
705
706         free(threads);
707         PTHREAD_VERIFY(pthread_cond_destroy(&self->cond));
708         PTHREAD_VERIFY(pthread_mutex_destroy(&self->mutex));
709
710         _serial_destroy(self);
711 }
712
713 #endif /* HAVE_PTHREAD */
714
715 int threadpool_create(struct threadpool *self, const struct threadpool_class *cls, Display *dpy, unsigned count)
716 {
717         (void)threads_available(dpy);
718
719         self->count = count;
720
721 /*      If threads are not present, run each "thread" in sequence on the calling
722         thread. Otherwise, only run the first thread on the main thread. */
723
724         assert(cls);
725
726         self->thread_size = cls->size;
727         self->thread_destroy = cls->destroy;
728
729         {
730                 void *thread;
731                 unsigned i, count_serial = _threadpool_count_serial(self);
732
733                 if(count_serial)
734                 {
735                         thread = malloc(cls->size * count_serial);
736                         if(!thread)
737                                 return ENOMEM;
738                 }
739                 else
740                 {
741                         /* Might as well skip the malloc. */
742                         thread = NULL;
743                 }
744
745                 self->serial_threads = thread;
746
747                 for(i = 0; i != count_serial; ++i)
748                 {
749                         int error = cls->create(thread, self, i);
750                         if(error)
751                         {
752                                 self->count = i;
753                                 _serial_destroy(self);
754                                 return error;
755                         }
756
757                         thread = (char *)thread + self->thread_size;
758                 }
759         }
760
761 #if HAVE_PTHREAD
762         assert(_has_pthread); /* _has_pthread should be either -1 or >0. */
763         if(_has_pthread >= 0)
764         {
765                 unsigned count_parallel = _threadpool_count_parallel(self);
766                 self->mutex = mutex_initializer;
767                 self->cond = cond_initializer;
768                 self->parallel_pending = 0;
769                 self->parallel_unfinished = 0;
770                 if(!count_parallel)
771                 {
772                         self->parallel_threads = NULL;
773                         return 0;
774                 }
775
776                 self->parallel_threads = malloc(sizeof(pthread_t) * count_parallel);
777                 if(!self->parallel_threads)
778                         return ENOMEM;
779
780                 {
781                         struct _parallel_startup_type startup;
782                         startup.parent = self;
783                         startup.thread_create = cls->create;
784                         startup.last_errno = 0;
785
786                         PTHREAD_VERIFY(pthread_mutex_lock(&self->mutex));
787                         _add_next_thread(&startup);
788
789                         if(!startup.last_errno)
790                         {
791                                 while(self->parallel_unfinished != count_parallel && self->parallel_threads)
792                                         PTHREAD_VERIFY(pthread_cond_wait(&self->cond, &self->mutex));
793                         }
794
795                         /* This must come after the if(!startup.last_errno). */
796                         if(startup.last_errno)
797                         {
798                                 _unlock_and_destroy(self);
799                         }
800                         else
801                         {
802                                 self->parallel_unfinished = 0;
803                                 PTHREAD_VERIFY(pthread_mutex_unlock(&self->mutex));
804                         }
805
806                         return startup.last_errno;
807                 }
808         }
809 #endif
810
811         return 0;
812 }
813
814 void threadpool_destroy(struct threadpool *self)
815 {
816 #if HAVE_PTHREAD
817         if(_has_pthread >= 0)
818         {
819                 PTHREAD_VERIFY(pthread_mutex_lock(&self->mutex));
820                 _unlock_and_destroy(self);
821                 return;
822         }
823 #endif
824
825         _serial_destroy(self);
826 }
827
828 void threadpool_run(struct threadpool *self, void (*func)(void *))
829 {
830 #if HAVE_PTHREAD
831         if(_has_pthread >= 0)
832         {
833                 unsigned count = _threadpool_count_parallel(self);
834                 PTHREAD_VERIFY(pthread_mutex_lock(&self->mutex));
835
836                 /* Do not call threadpool_run() twice without a threadpool_wait() in the middle. */
837                 assert(!self->parallel_pending);
838                 assert(!self->parallel_unfinished);
839
840                 self->parallel_pending = count;
841                 self->parallel_unfinished = count;
842                 self->thread_run = func;
843                 PTHREAD_VERIFY(pthread_cond_broadcast(&self->cond));
844                 PTHREAD_VERIFY(pthread_mutex_unlock(&self->mutex));
845         }
846 #endif
847
848         /* It's perfectly valid to move this to the beginning of threadpool_wait(). */
849         {
850                 void *thread = self->serial_threads;
851                 unsigned i, count = _threadpool_count_serial(self);
852                 for(i = 0; i != count; ++i)
853                 {
854                         func(thread);
855                         thread = (char *)thread + self->thread_size;
856                 }
857         }
858 }
859
860 void threadpool_wait(struct threadpool *self)
861 {
862 #if HAVE_PTHREAD
863         if(_has_pthread >= 0)
864         {
865                 PTHREAD_VERIFY(pthread_mutex_lock(&self->mutex));
866                 while(self->parallel_unfinished)
867                         PTHREAD_VERIFY(pthread_cond_wait(&self->cond, &self->mutex));
868                 PTHREAD_VERIFY(pthread_mutex_unlock(&self->mutex));
869         }
870 #endif
871 }
872
873 /* io_thread - */
874
875 #if HAVE_PTHREAD
876 /* Without threads at compile time, there's only stubs in thread_util.h. */
877
878 #       define VERSION_CHECK(cc_major, cc_minor, req_major, req_minor) \
879         ((cc_major) > (req_major) || \
880         (cc_major) == (req_major) && (cc_minor) >= (req_minor))
881
882 #       if defined(__GNUC__) && (__GNUC__ > 4 || __GNUC__ == 4 && __GNUC_MINOR__ >= 7) || \
883         defined(__clang__) && \
884                 (!defined(__apple_build_version__) && VERSION_CHECK(__clang_major__, __clang_minor__, 3, 1) || \
885                   defined(__apple_build_version__) && VERSION_CHECK(__clang_major__, __clang_minor__, 3, 1)) || \
886         defined(__ICC) && __ICC >= 1400
887
888 /*
889    Clang 3.0 has a partial implementation of GNU atomics; 3.1 rounds it out.
890    http://llvm.org/viewvc/llvm-project/cfe/tags/RELEASE_30/final/include/clang/Basic/Builtins.def?view=markup
891    http://llvm.org/viewvc/llvm-project/cfe/tags/RELEASE_31/final/include/clang/Basic/Builtins.def?view=markup
892
893    Apple changes the Clang version to track Xcode versions; use
894    __apple_build_version__ to distinguish between the two.
895
896    Xcode 4.3 uses Apple LLVM 3.1, which corresponds to Clang 3.1.
897    https://en.wikipedia.org/wiki/Xcode
898
899    Earlier versions of Intel C++ may also support these intrinsics.
900  */
901
902 #define _status_load(status) (__atomic_load_n((status), __ATOMIC_SEQ_CST))
903 #define _status_exchange(obj, desired) (__atomic_exchange_n((obj), (desired), __ATOMIC_SEQ_CST))
904
905 /* C11 atomics are around the corner, but they're not here yet for many
906    systems. (Including mine.) */
907 /*
908 #elif __STDC_VERSION__ >= 201112l && !defined __STDC_NO_ATOMICS__
909
910 #include <stdatomic.h>
911
912 #define _status_load(status) (atomic_load((status)))
913 #define _status_exchange(obj, desired) (atomic_exchange((obj), (desired)))
914 */
915
916 /* Solaris profiles atomic ops on at least Solaris 10. See atomic_swap(3C) and
917    membar_ops(3C). This would probably also need a snippet in configure.in.
918    http://graegert.com/programming/using-atomic-operations-in-c-on-solaris-10
919 */
920
921 #       else
922
923 /* No atomic variables, so here's some ugly mutex-based code instead. */
924
925 /* Nothing ever destroys this mutex. */
926 pthread_mutex_t _global_mutex = PTHREAD_MUTEX_INITIALIZER;
927
928 #define _lock() PTHREAD_VERIFY(pthread_mutex_lock(&_global_mutex))
929 #define _unlock() PTHREAD_VERIFY(pthread_mutex_unlock(&_global_mutex))
930
931 static enum _io_thread_status _status_load(enum _io_thread_status *status)
932 {
933         enum _io_thread_status result;
934         _lock();
935         result = *status;
936         _unlock();
937         return result;
938 }
939
940 static enum _io_thread_status _status_exchange(enum _io_thread_status *obj, enum _io_thread_status desired)
941 {
942         enum _io_thread_status result;
943         _lock();
944         result = *obj;
945         *obj = desired;
946         _unlock();
947         return result;
948 }
949
950 #       endif
951
952 void *io_thread_create(struct io_thread *self, void *parent, void *(*start_routine)(void *), Display *dpy, unsigned stacksize)
953 {
954         if(threads_available(dpy) >= 0)
955         {
956                 int error;
957                 pthread_attr_t attr;
958                 pthread_attr_t *attr_ptr = NULL;
959
960                 if(stacksize)
961                 {
962                         attr_ptr = &attr;
963                         if(pthread_attr_init(&attr))
964                                 return NULL;
965 #   if defined _POSIX_SOURCE || defined _POSIX_C_SOURCE || defined _XOPEN_SOURCE
966                         /* PTHREAD_STACK_MIN needs the above test. */
967                         assert(stacksize >= PTHREAD_STACK_MIN);
968 #   endif
969                         PTHREAD_VERIFY(pthread_attr_setstacksize(&attr, stacksize));
970                 }
971
972                 /* This doesn't need to be an atomic store, since pthread_create(3)
973                    "synchronizes memory with respect to other threads".
974                    http://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1_chap04.html#tag_04_11 */
975                 self->status = _io_thread_working;
976
977                 error = pthread_create(&self->thread, attr_ptr, start_routine, parent);
978                 assert(!error || error == EAGAIN);
979                 if(error)
980                         parent = NULL;
981
982                 if(attr_ptr)
983                         PTHREAD_VERIFY(pthread_attr_destroy(attr_ptr));
984
985                 return parent;
986         }
987
988         return NULL;
989 }
990
991 int io_thread_return(struct io_thread *self)
992 {
993         if(_has_pthread >= 0)
994         {
995                 enum _io_thread_status old_status = _status_exchange(&self->status, _io_thread_done);
996                 assert(old_status == _io_thread_working ||
997                        old_status == _io_thread_cancelled);
998                 return old_status != _io_thread_working;
999         }
1000
1001         return 0;
1002 }
1003
1004 int io_thread_is_done(struct io_thread *self)
1005 {
1006         if(_has_pthread >= 0)
1007         {
1008                 int result = _status_load(&self->status);
1009                 assert(result != _io_thread_cancelled);
1010                 return result;
1011         }
1012         return 1;
1013 }
1014
1015 int io_thread_cancel(struct io_thread *self)
1016 {
1017         if(_has_pthread >= 0)
1018         {
1019                 enum _io_thread_status old_status =
1020                         _status_exchange(&self->status, _io_thread_cancelled);
1021                 assert(old_status == _io_thread_working ||
1022                        old_status == _io_thread_done);
1023
1024                 PTHREAD_VERIFY(pthread_detach(self->thread));
1025                 return old_status != _io_thread_working;
1026         }
1027
1028         return 0;
1029 }
1030
1031 void io_thread_finish(struct io_thread *self)
1032 {
1033         if(_has_pthread >= 0)
1034         {
1035 #       ifndef NDEBUG
1036                 enum _io_thread_status status = _status_load(&self->status);
1037                 assert(status == _io_thread_working ||
1038                        status == _io_thread_done);
1039 #       endif
1040                 PTHREAD_VERIFY(pthread_join(self->thread, NULL));
1041                 assert(_status_load(&self->status) == _io_thread_done);
1042         }
1043 }
1044
1045 #endif /* HAVE_PTHREAD */