1 /*
  2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  3  *
  4  * This code is free software; you can redistribute it and/or modify it
  5  * under the terms of the GNU General Public License version 2 only, as
  6  * published by the Free Software Foundation.  Oracle designates this
  7  * particular file as subject to the "Classpath" exception as provided
  8  * by Oracle in the LICENSE file that accompanied this code.
  9  *
 10  * This code is distributed in the hope that it will be useful, but WITHOUT
 11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 12  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 13  * version 2 for more details (a copy is included in the LICENSE file that
 14  * accompanied this code).
 15  *
 16  * You should have received a copy of the GNU General Public License version
 17  * 2 along with this work; if not, write to the Free Software Foundation,
 18  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 19  *
 20  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 21  * or visit www.oracle.com if you need additional information or have any
 22  * questions.
 23  */
 24 
 25 /*
 26  * This file is available under and governed by the GNU General Public
 27  * License version 2 only, as published by the Free Software Foundation.
 28  * However, the following notice accompanied the original version of this
 29  * file:
 30  *
 31  * Written by Doug Lea with assistance from members of JCP JSR-166
 32  * Expert Group and released to the public domain, as explained at
 33  * http://creativecommons.org/publicdomain/zero/1.0/
 34  *
 35  * Additional modifications by Guy Steele in 2019 to refactor the code
 36  * and to implement the {@link RandomGenerator} interface.
 37  */
 38 
 39 package java.util.concurrent;
 40 
 41 import java.io.ObjectStreamField;
 42 import java.math.BigInteger;
 43 import java.security.AccessControlContext;
 44 import java.util.Map;
 45 import java.util.Random;
 46 import java.util.Spliterator;
 47 import java.util.concurrent.atomic.AtomicInteger;
 48 import java.util.concurrent.atomic.AtomicLong;
 49 import java.util.random.RandomGenerator;
 50 import java.util.stream.DoubleStream;
 51 import java.util.stream.IntStream;
 52 import java.util.stream.LongStream;
 53 import jdk.internal.util.random.RandomSupport;
 54 import jdk.internal.util.random.RandomSupport.*;
 55 import jdk.internal.misc.Unsafe;
 56 import jdk.internal.misc.VM;
 57 
 58 /**
 59  * A random number generator (with period 2<sup>64</sup>) isolated
 60  * to the current thread.  Like the global {@link java.util.Random}
 61  * generator used by the {@link java.lang.Math} class,
 62  * a {@code ThreadLocalRandom} is initialized
 63  * with an internally generated seed that may not otherwise be
 64  * modified. When applicable, use of {@code ThreadLocalRandom} rather
 65  * than shared {@code Random} objects in concurrent programs will
 66  * typically encounter much less overhead and contention.  Use of
 67  * {@code ThreadLocalRandom} is particularly appropriate when multiple
 68  * tasks (for example, each a {@link ForkJoinTask}) use random numbers
 69  * in parallel in thread pools.
 70  *
 71  * <p>Usages of this class should typically be of the form:
 72  * {@code ThreadLocalRandom.current().nextX(...)} (where
 73  * {@code X} is {@code Int}, {@code Long}, etc).
 74  * When all usages are of this form, it is never possible to
 75  * accidentally share a {@code ThreadLocalRandom} across multiple threads.
 76  *
 77  * <p>This class also provides additional commonly used bounded random
 78  * generation methods.
 79  *
 80  * <p>Instances of {@code ThreadLocalRandom} are not cryptographically
 81  * secure.  Consider instead using {@link java.security.SecureRandom}
 82  * in security-sensitive applications. Additionally,
 83  * default-constructed instances do not use a cryptographically random
 84  * seed unless the {@linkplain System#getProperty system property}
 85  * {@code java.util.secureRandomSeed} is set to {@code true}.
 86  *
 87  * @since 1.7
 88  * @author Doug Lea
 89  */
 90 
 91 @RandomGeneratorProperties(
 92         name = "ThreadLocalRandom",
 93         i = 64, j = 0, k = 0,
 94         equidistribution = 1
 95 )
 96 public class ThreadLocalRandom extends Random {
 97     /*
 98      * This class implements the java.util.Random API (and subclasses
 99      * Random) using a single static instance that accesses 64 bits of
100      * random number state held in class java.lang.Thread (field
101      * threadLocalRandomSeed). In doing so, it also provides a home
102      * for managing package-private utilities that rely on exactly the
103      * same state as needed to maintain the ThreadLocalRandom
104      * instances. We leverage the need for an initialization flag
105      * field to also use it as a "probe" -- a self-adjusting thread
106      * hash used for contention avoidance, as well as a secondary
107      * simpler (xorShift) random seed that is conservatively used to
108      * avoid otherwise surprising users by hijacking the
109      * ThreadLocalRandom sequence.  The dual use is a marriage of
110      * convenience, but is a simple and efficient way of reducing
111      * application-level overhead and footprint of most concurrent
112      * programs. Even more opportunistically, we also define here
113      * other package-private utilities that access Thread class
114      * fields.
115      *
116      * Even though this class subclasses java.util.Random, it uses the
117      * same basic algorithm as java.util.SplittableRandom.  (See its
118      * internal documentation for explanations, which are not repeated
119      * here.)  Note that ThreadLocalRandom is not a "splittable" generator
120      * (it does not support the split method), but it behaves as if
121      * one instance of the SplittableRandom algorithm had been
122      * created for each thread, each with a distinct gamma parameter
123      * (calculated from the thread id).
124      *
125      * Because this class is in a different package than class Thread,
126      * field access methods use Unsafe to bypass access control rules.
127      * To conform to the requirements of the Random superclass
128      * constructor, the common static ThreadLocalRandom maintains an
129      * "initialized" field for the sake of rejecting user calls to
130      * setSeed while still allowing a call from constructor.  Note
131      * that serialization is completely unnecessary because there is
132      * only a static singleton.  But we generate a serial form
133      * containing "rnd" and "initialized" fields to ensure
134      * compatibility across versions.
135      *
136      * Implementations of non-core methods are mostly the same as in
137      * SplittableRandom, that were in part derived from a previous
138      * version of this class.
139      *
140      * This implementation of ThreadLocalRandom overrides the
141      * definition of the nextGaussian() method in the class Random,
142      * and instead uses the ziggurat-based algorithm that is the
143      * default for the RandomGenerator interface.
144      */
145 
146     private static int mix32(long z) {
147         z = (z ^ (z >>> 33)) * 0xff51afd7ed558ccdL;
148         return (int)(((z ^ (z >>> 33)) * 0xc4ceb9fe1a85ec53L) >>> 32);
149     }
150 
151     /**
152      * Field used only during singleton initialization.
153      * True when constructor completes.
154      */
155     boolean initialized;
156 
157     /** Constructor used only for static singleton */
158     private ThreadLocalRandom() {
159         initialized = true; // false during super() call
160     }
161 
162     /**
163      * Initialize Thread fields for the current thread.  Called only
164      * when Thread.threadLocalRandomProbe is zero, indicating that a
165      * thread local seed value needs to be generated. Note that even
166      * though the initialization is purely thread-local, we need to
167      * rely on (static) atomic generators to initialize the values.
168      */
169     static final void localInit() {
170         int p = probeGenerator.addAndGet(PROBE_INCREMENT);
171         int probe = (p == 0) ? 1 : p; // skip 0
172         long seed = RandomSupport.mixMurmur64(seeder.getAndAdd(SEEDER_INCREMENT));
173         Thread t = Thread.currentThread();
174         U.putLong(t, SEED, seed);
175         U.putInt(t, PROBE, probe);
176     }
177 
178     /**
179      * Returns the current thread's {@code ThreadLocalRandom} object.
180      * Methods of this object should be called only by the current thread,
181      * not by other threads.
182      *
183      * @return the current thread's {@code ThreadLocalRandom}
184      */
185     public static ThreadLocalRandom current() {
186         if (U.getInt(Thread.currentThread(), PROBE) == 0)
187             localInit();
188         return instance;
189     }
190 
191     /**
192      * Throws {@code UnsupportedOperationException}.  Setting seeds in
193      * this generator is not supported.
194      *
195      * @throws UnsupportedOperationException always
196      */
197     public void setSeed(long seed) {
198         // only allow call from super() constructor
199         if (initialized)
200             throw new UnsupportedOperationException();
201     }
202 
203     /**
204      * Update the thread local seed value by adding to it the sum
205      * of {@code GOLDEN_GAMMA} (an odd value) and twice the thread id.
206      * This sum is always odd (to guarantee that the generator
207      * has maximum period) and is different for different threads.
208      * Because thread id values are allocated consecutively starting
209      * from 0, the high 32 bits of this sum will be the same as the
210      * high 32 bits of {@code GOLDEN_GAMMA} unless an extremely large
211      * number of threads have been created, and so the overall
212      * value added to the thread local seed value will have at least
213      * fourteen 01 and 10 transitions (see the documentation for the
214      * method {@code mixGamma} in class {@code SplittableRandom}),
215      * which should provide adequate statistical quality for
216      * applications likely to use {@code ThreadLocalRandom}.
217      */
218     final long nextSeed() {
219         Thread t; long r; // read and update per-thread seed
220         U.putLong(t = Thread.currentThread(), SEED,
221                   r = U.getLong(t, SEED) + (t.getId() << 1) + GOLDEN_GAMMA);
222         return r;
223     }
224 
225     /**
226      * Generates a pseudorandom number with the indicated number of
227      * low-order bits.  Because this class has no subclasses, this
228      * method cannot be invoked or overridden.
229      *
230      * @param  bits random bits
231      * @return the next pseudorandom value from this random number
232      *         generator's sequence
233      */
234     protected int next(int bits) {
235         return nextInt() >>> (32 - bits);
236     }
237 
238     // Within-package utilities
239 
240     /*
241      * Descriptions of the usages of the methods below can be found in
242      * the classes that use them. Briefly, a thread's "probe" value is
243      * a non-zero hash code that (probably) does not collide with
244      * other existing threads with respect to any power of two
245      * collision space. When it does collide, it is pseudo-randomly
246      * adjusted (using a Marsaglia XorShift). The nextSecondarySeed
247      * method is used in the same contexts as ThreadLocalRandom, but
248      * only for transient usages such as random adaptive spin/block
249      * sequences for which a cheap RNG suffices and for which it could
250      * in principle disrupt user-visible statistical properties of the
251      * main ThreadLocalRandom if we were to use it.
252      *
253      * Note: Because of package-protection issues, versions of some
254      * these methods also appear in some subpackage classes.
255      */
256 
257     /**
258      * Returns the probe value for the current thread without forcing
259      * initialization. Note that invoking ThreadLocalRandom.current()
260      * can be used to force initialization on zero return.
261      */
262     static final int getProbe() {
263         return U.getInt(Thread.currentThread(), PROBE);
264     }
265 
266     /**
267      * Pseudo-randomly advances and records the given probe value for the
268      * given thread.
269      */
270     static final int advanceProbe(int probe) {
271         probe ^= probe << 13;   // xorshift
272         probe ^= probe >>> 17;
273         probe ^= probe << 5;
274         U.putInt(Thread.currentThread(), PROBE, probe);
275         return probe;
276     }
277 
278     /**
279      * Returns the pseudo-randomly initialized or updated secondary seed.
280      */
281     static final int nextSecondarySeed() {
282         int r;
283         Thread t = Thread.currentThread();
284         if ((r = U.getInt(t, SECONDARY)) != 0) {
285             r ^= r << 13;   // xorshift
286             r ^= r >>> 17;
287             r ^= r << 5;
288         }
289         else if ((r = mix32(seeder.getAndAdd(SEEDER_INCREMENT))) == 0)
290             r = 1; // avoid zero
291         U.putInt(t, SECONDARY, r);
292         return r;
293     }
294 
295     // Support for other package-private ThreadLocal access
296 
297     /**
298      * Erases ThreadLocals by nulling out Thread maps.
299      */
300     static final void eraseThreadLocals(Thread thread) {
301         U.putReference(thread, THREADLOCALS, null);
302         U.putReference(thread, INHERITABLETHREADLOCALS, null);
303     }
304 
305     static final void setInheritedAccessControlContext(Thread thread,
306                                                        @SuppressWarnings("removal") AccessControlContext acc) {
307         U.putReferenceRelease(thread, INHERITEDACCESSCONTROLCONTEXT, acc);
308     }
309 
310     // Serialization support
311 
312     private static final long serialVersionUID = -5851777807851030925L;
313 
314     /**
315      * @serialField rnd long
316      *              seed for random computations
317      * @serialField initialized boolean
318      *              always true
319      */
320     private static final ObjectStreamField[] serialPersistentFields = {
321         new ObjectStreamField("rnd", long.class),
322         new ObjectStreamField("initialized", boolean.class),
323     };
324 
325     /**
326      * Saves the {@code ThreadLocalRandom} to a stream (that is, serializes it).
327      * @param s the stream
328      * @throws java.io.IOException if an I/O error occurs
329      */
330     private void writeObject(java.io.ObjectOutputStream s)
331         throws java.io.IOException {
332 
333         java.io.ObjectOutputStream.PutField fields = s.putFields();
334         fields.put("rnd", U.getLong(Thread.currentThread(), SEED));
335         fields.put("initialized", true);
336         s.writeFields();
337     }
338 
339     /**
340      * Returns the {@link #current() current} thread's {@code ThreadLocalRandom}.
341      * @return the {@link #current() current} thread's {@code ThreadLocalRandom}
342      */
343     private Object readResolve() {
344         return current();
345     }
346 
347     // Static initialization
348 
349     /**
350      * The seed increment.  This must be an odd value for the generator to
351      * have the maximum period (2 to the 64th power).
352      *
353      * The value 0x9e3779b97f4a7c15L is odd, and moreover consists of the
354      * first 64 bits of the fractional part of the golden ratio,
355      * which is known to generate good Weyl sequences.
356      */
357     private static final long GOLDEN_GAMMA = 0x9e3779b97f4a7c15L;
358 
359     /**
360      * The increment for generating probe values.
361      */
362     private static final int PROBE_INCREMENT = 0x9e3779b9;
363 
364     /**
365      * The increment of seeder per new instance.
366      */
367     private static final long SEEDER_INCREMENT = 0xbb67ae8584caa73bL;
368 
369     // IllegalArgumentException messages
370     static final String BAD_BOUND = "bound must be positive";
371     static final String BAD_RANGE = "bound must be greater than origin";
372     static final String BAD_SIZE  = "size must be non-negative";
373 
374     // Unsafe mechanics
375     private static final Unsafe U = Unsafe.getUnsafe();
376     private static final long SEED
377         = U.objectFieldOffset(Thread.class, "threadLocalRandomSeed");
378     private static final long PROBE
379         = U.objectFieldOffset(Thread.class, "threadLocalRandomProbe");
380     private static final long SECONDARY
381         = U.objectFieldOffset(Thread.class, "threadLocalRandomSecondarySeed");
382     private static final long THREADLOCALS
383         = U.objectFieldOffset(Thread.class, "threadLocals");
384     private static final long INHERITABLETHREADLOCALS
385         = U.objectFieldOffset(Thread.class, "inheritableThreadLocals");
386     private static final long INHERITEDACCESSCONTROLCONTEXT
387         = U.objectFieldOffset(Thread.class, "inheritedAccessControlContext");
388 
389     /** Generates per-thread initialization/probe field */
390     private static final AtomicInteger probeGenerator = new AtomicInteger();
391 
392     /** The common ThreadLocalRandom */
393     private static final ThreadLocalRandom instance = new ThreadLocalRandom();
394 
395     /**
396      * The next seed for default constructors.
397      */
398     private static final AtomicLong seeder
399         = new AtomicLong(RandomSupport.mixMurmur64(System.currentTimeMillis()) ^
400                          RandomSupport.mixMurmur64(System.nanoTime()));
401 
402     // at end of <clinit> to survive static initialization circularity
403     static {
404         String sec = VM.getSavedProperty("java.util.secureRandomSeed");
405         if (Boolean.parseBoolean(sec)) {
406             byte[] seedBytes = java.security.SecureRandom.getSeed(8);
407             long s = (long)seedBytes[0] & 0xffL;
408             for (int i = 1; i < 8; ++i)
409                 s = (s << 8) | ((long)seedBytes[i] & 0xffL);
410             seeder.set(s);
411         }
412     }
413 
414     @SuppressWarnings("serial")
415     private static final class ThreadLocalRandomProxy extends Random {
416         static final Random PROXY = new ThreadLocalRandomProxy();
417 
418         public int nextInt() {
419             return ThreadLocalRandom.current().nextInt();
420         }
421 
422         public long nextLong() {
423             return ThreadLocalRandom.current().nextLong();
424         }
425     }
426 
427     /**
428      * {@inheritDoc}
429      */
430     @Override
431     public boolean nextBoolean() {
432         return super.nextBoolean();
433     }
434 
435     /**
436      * {@inheritDoc}
437      */
438     @Override
439     public int nextInt() {
440         return mix32(nextSeed());
441     }
442 
443     /**
444      * {@inheritDoc}
445      * @throws IllegalArgumentException {@inheritDoc}
446      */
447     @Override
448     public int nextInt(int bound) {
449         return super.nextInt(bound);
450     }
451 
452     /**
453      * {@inheritDoc}
454      * @throws IllegalArgumentException {@inheritDoc}
455      */
456     @Override
457     public int nextInt(int origin, int bound) {
458         return super.nextInt(origin, bound);
459     }
460 
461     /**
462      * {@inheritDoc}
463      */
464     @Override
465     public long nextLong() {
466         return RandomSupport.mixMurmur64(nextSeed());
467     }
468 
469     /**
470      * {@inheritDoc}
471      * @throws IllegalArgumentException {@inheritDoc}
472      */
473     @Override
474     public long nextLong(long bound) {
475         return super.nextLong(bound);
476     }
477 
478     /**
479      * {@inheritDoc}
480      * @throws IllegalArgumentException {@inheritDoc}
481      */
482     @Override
483     public long nextLong(long origin, long bound) {
484         return super.nextLong(origin, bound);
485     }
486 
487     /**
488      * {@inheritDoc}
489      */
490     @Override
491     public float nextFloat() {
492         return super.nextFloat();
493     }
494 
495     /**
496      * {@inheritDoc}
497      * @throws IllegalArgumentException {@inheritDoc}
498      * @implNote {@inheritDoc}
499      */
500     @Override
501     public float nextFloat(float bound) {
502          return super.nextFloat(bound);
503     }
504 
505     /**
506      * {@inheritDoc}
507      * @throws IllegalArgumentException {@inheritDoc}
508      * @implNote {@inheritDoc}
509      */
510     @Override
511     public float nextFloat(float origin, float bound) {
512         return super.nextFloat(origin, bound);
513     }
514 
515     /**
516      * {@inheritDoc}
517      */
518     @Override
519     public double nextDouble() {
520         return super.nextDouble();
521     }
522 
523     /**
524      * {@inheritDoc}
525      * @throws IllegalArgumentException {@inheritDoc}
526      * @implNote {@inheritDoc}
527      */
528     @Override
529     public double nextDouble(double bound) {
530         return super.nextDouble(bound);
531     }
532 
533     /**
534      * {@inheritDoc}
535      * @throws IllegalArgumentException {@inheritDoc}
536      * @implNote {@inheritDoc}
537      */
538     @Override
539     public double nextDouble(double origin, double bound) {
540         return super.nextDouble(origin, bound);
541     }
542     /**
543      * {@inheritDoc}
544      * @throws IllegalArgumentException {@inheritDoc}
545      * @since 1.8
546      */
547     @Override
548     public IntStream ints(long streamSize) {
549         return AbstractSpliteratorGenerator.ints(ThreadLocalRandomProxy.PROXY, streamSize);
550     }
551 
552     /**
553      * {@inheritDoc}
554      * @implNote This method is implemented to be equivalent to
555      *           {@code ints(Long.MAX_VALUE)}.
556      * @since 1.8
557      */
558     @Override
559     public IntStream ints() {
560         return AbstractSpliteratorGenerator.ints(ThreadLocalRandomProxy.PROXY);
561     }
562 
563     /**
564      * {@inheritDoc}
565      * @throws IllegalArgumentException {@inheritDoc}
566      * @since 1.8
567      */
568     @Override
569     public IntStream ints(long streamSize, int randomNumberOrigin, int randomNumberBound) {
570         return AbstractSpliteratorGenerator.ints(ThreadLocalRandomProxy.PROXY, streamSize, randomNumberOrigin, randomNumberBound);
571     }
572 
573     /**
574      * {@inheritDoc}
575      * @implNote This method is implemented to be equivalent to
576      *           {@code ints(Long.MAX_VALUE, randomNumberOrigin, randomNumberBound)}.
577      * @throws IllegalArgumentException {@inheritDoc}
578      * @since 1.8
579      */
580     @Override
581     public IntStream ints(int randomNumberOrigin, int randomNumberBound) {
582         return AbstractSpliteratorGenerator.ints(ThreadLocalRandomProxy.PROXY, randomNumberOrigin, randomNumberBound);
583     }
584 
585     /**
586      * {@inheritDoc}
587      * @throws IllegalArgumentException {@inheritDoc}
588      * @since 1.8
589      */
590     @Override
591     public LongStream longs(long streamSize) {
592         return AbstractSpliteratorGenerator.longs(ThreadLocalRandomProxy.PROXY, streamSize);
593     }
594 
595     /**
596      * {@inheritDoc}
597      * @implNote This method is implemented to be equivalent to
598      *           {@code longs(Long.MAX_VALUE)}.
599      * @since 1.8
600      */
601     @Override
602     public LongStream longs() {
603         return AbstractSpliteratorGenerator.longs(ThreadLocalRandomProxy.PROXY);
604     }
605 
606     /**
607      * {@inheritDoc}
608      * @throws IllegalArgumentException {@inheritDoc}
609      * @since 1.8
610      */
611     @Override
612     public LongStream longs(long streamSize, long randomNumberOrigin, long randomNumberBound) {
613         return AbstractSpliteratorGenerator.longs(ThreadLocalRandomProxy.PROXY, streamSize, randomNumberOrigin, randomNumberBound);
614     }
615 
616     /**
617      * {@inheritDoc}
618      * @implNote This method is implemented to be equivalent to
619      *           {@code longs(Long.MAX_VALUE, randomNumberOrigin, randomNumberBound)}.
620      * @throws IllegalArgumentException {@inheritDoc}
621      * @since 1.8
622      */
623     @Override
624     public LongStream longs(long randomNumberOrigin, long randomNumberBound) {
625         return AbstractSpliteratorGenerator.longs(ThreadLocalRandomProxy.PROXY, randomNumberOrigin, randomNumberBound);
626     }
627 
628     /**
629      * {@inheritDoc}
630      * @throws IllegalArgumentException {@inheritDoc}
631      * @since 1.8
632      */
633     @Override
634     public DoubleStream doubles(long streamSize) {
635         return AbstractSpliteratorGenerator.doubles(ThreadLocalRandomProxy.PROXY, streamSize);
636     }
637 
638     /**
639      * {@inheritDoc}
640      * @implNote This method is implemented to be equivalent to
641      *           {@code doubles(Long.MAX_VALUE)}.
642      * @since 1.8
643      */
644     @Override
645     public DoubleStream doubles() {
646         return AbstractSpliteratorGenerator.doubles(ThreadLocalRandomProxy.PROXY);
647     }
648 
649     /**
650      * {@inheritDoc}
651      * @throws IllegalArgumentException {@inheritDoc}
652      * @since 1.8
653      */
654     @Override
655     public DoubleStream doubles(long streamSize, double randomNumberOrigin, double randomNumberBound) {
656         return AbstractSpliteratorGenerator.doubles(ThreadLocalRandomProxy.PROXY, streamSize, randomNumberOrigin, randomNumberBound);
657     }
658 
659     /**
660      * {@inheritDoc}
661      * @implNote This method is implemented to be equivalent to
662      *           {@code doubles(Long.MAX_VALUE, randomNumberOrigin, randomNumberBound)}.
663      * @throws IllegalArgumentException {@inheritDoc}
664      * @since 1.8
665      */
666     @Override
667     public DoubleStream doubles(double randomNumberOrigin, double randomNumberBound) {
668         return AbstractSpliteratorGenerator.doubles(ThreadLocalRandomProxy.PROXY, randomNumberOrigin, randomNumberBound);
669     }
670 
671 }