diff options
Diffstat (limited to 'include/jemalloc/internal/prng.h')
| -rw-r--r-- | include/jemalloc/internal/prng.h | 140 |
1 files changed, 59 insertions, 81 deletions
diff --git a/include/jemalloc/internal/prng.h b/include/jemalloc/internal/prng.h index c2bda19..15cc2d1 100644 --- a/include/jemalloc/internal/prng.h +++ b/include/jemalloc/internal/prng.h @@ -1,5 +1,8 @@ -/******************************************************************************/ -#ifdef JEMALLOC_H_TYPES +#ifndef JEMALLOC_INTERNAL_PRNG_H +#define JEMALLOC_INTERNAL_PRNG_H + +#include "jemalloc/internal/atomic.h" +#include "jemalloc/internal/bit_util.h" /* * Simple linear congruential pseudo-random number generator: @@ -20,95 +23,71 @@ * bits. */ -#define PRNG_A_32 UINT32_C(1103515241) -#define PRNG_C_32 UINT32_C(12347) - -#define PRNG_A_64 UINT64_C(6364136223846793005) -#define PRNG_C_64 UINT64_C(1442695040888963407) - -#endif /* JEMALLOC_H_TYPES */ /******************************************************************************/ -#ifdef JEMALLOC_H_STRUCTS - -#endif /* JEMALLOC_H_STRUCTS */ -/******************************************************************************/ -#ifdef JEMALLOC_H_EXTERNS - -#endif /* JEMALLOC_H_EXTERNS */ +/* INTERNAL DEFINITIONS -- IGNORE */ /******************************************************************************/ -#ifdef JEMALLOC_H_INLINES +#define PRNG_A_32 UINT32_C(1103515241) +#define PRNG_C_32 UINT32_C(12347) -#ifndef JEMALLOC_ENABLE_INLINE -uint32_t prng_state_next_u32(uint32_t state); -uint64_t prng_state_next_u64(uint64_t state); -size_t prng_state_next_zu(size_t state); +#define PRNG_A_64 UINT64_C(6364136223846793005) +#define PRNG_C_64 UINT64_C(1442695040888963407) -uint32_t prng_lg_range_u32(uint32_t *state, unsigned lg_range, - bool atomic); -uint64_t prng_lg_range_u64(uint64_t *state, unsigned lg_range); -size_t prng_lg_range_zu(size_t *state, unsigned lg_range, bool atomic); - -uint32_t prng_range_u32(uint32_t *state, uint32_t range, bool atomic); -uint64_t prng_range_u64(uint64_t *state, uint64_t range); -size_t prng_range_zu(size_t *state, size_t range, bool atomic); -#endif - -#if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_PRNG_C_)) JEMALLOC_ALWAYS_INLINE uint32_t -prng_state_next_u32(uint32_t state) -{ - - return ((state * PRNG_A_32) + PRNG_C_32); +prng_state_next_u32(uint32_t state) { + return (state * PRNG_A_32) + PRNG_C_32; } JEMALLOC_ALWAYS_INLINE uint64_t -prng_state_next_u64(uint64_t state) -{ - - return ((state * PRNG_A_64) + PRNG_C_64); +prng_state_next_u64(uint64_t state) { + return (state * PRNG_A_64) + PRNG_C_64; } JEMALLOC_ALWAYS_INLINE size_t -prng_state_next_zu(size_t state) -{ - +prng_state_next_zu(size_t state) { #if LG_SIZEOF_PTR == 2 - return ((state * PRNG_A_32) + PRNG_C_32); + return (state * PRNG_A_32) + PRNG_C_32; #elif LG_SIZEOF_PTR == 3 - return ((state * PRNG_A_64) + PRNG_C_64); + return (state * PRNG_A_64) + PRNG_C_64; #else #error Unsupported pointer size #endif } +/******************************************************************************/ +/* BEGIN PUBLIC API */ +/******************************************************************************/ + +/* + * The prng_lg_range functions give a uniform int in the half-open range [0, + * 2**lg_range). If atomic is true, they do so safely from multiple threads. + * Multithreaded 64-bit prngs aren't supported. + */ + JEMALLOC_ALWAYS_INLINE uint32_t -prng_lg_range_u32(uint32_t *state, unsigned lg_range, bool atomic) -{ - uint32_t ret, state1; +prng_lg_range_u32(atomic_u32_t *state, unsigned lg_range, bool atomic) { + uint32_t ret, state0, state1; assert(lg_range > 0); assert(lg_range <= 32); - if (atomic) { - uint32_t state0; + state0 = atomic_load_u32(state, ATOMIC_RELAXED); + if (atomic) { do { - state0 = atomic_read_uint32(state); state1 = prng_state_next_u32(state0); - } while (atomic_cas_uint32(state, state0, state1)); + } while (!atomic_compare_exchange_weak_u32(state, &state0, + state1, ATOMIC_RELAXED, ATOMIC_RELAXED)); } else { - state1 = prng_state_next_u32(*state); - *state = state1; + state1 = prng_state_next_u32(state0); + atomic_store_u32(state, state1, ATOMIC_RELAXED); } ret = state1 >> (32 - lg_range); - return (ret); + return ret; } -/* 64-bit atomic operations cannot be supported on all relevant platforms. */ JEMALLOC_ALWAYS_INLINE uint64_t -prng_lg_range_u64(uint64_t *state, unsigned lg_range) -{ +prng_lg_range_u64(uint64_t *state, unsigned lg_range) { uint64_t ret, state1; assert(lg_range > 0); @@ -118,36 +97,39 @@ prng_lg_range_u64(uint64_t *state, unsigned lg_range) *state = state1; ret = state1 >> (64 - lg_range); - return (ret); + return ret; } JEMALLOC_ALWAYS_INLINE size_t -prng_lg_range_zu(size_t *state, unsigned lg_range, bool atomic) -{ - size_t ret, state1; +prng_lg_range_zu(atomic_zu_t *state, unsigned lg_range, bool atomic) { + size_t ret, state0, state1; assert(lg_range > 0); assert(lg_range <= ZU(1) << (3 + LG_SIZEOF_PTR)); - if (atomic) { - size_t state0; + state0 = atomic_load_zu(state, ATOMIC_RELAXED); + if (atomic) { do { - state0 = atomic_read_z(state); state1 = prng_state_next_zu(state0); - } while (atomic_cas_z(state, state0, state1)); + } while (atomic_compare_exchange_weak_zu(state, &state0, + state1, ATOMIC_RELAXED, ATOMIC_RELAXED)); } else { - state1 = prng_state_next_zu(*state); - *state = state1; + state1 = prng_state_next_zu(state0); + atomic_store_zu(state, state1, ATOMIC_RELAXED); } ret = state1 >> ((ZU(1) << (3 + LG_SIZEOF_PTR)) - lg_range); - return (ret); + return ret; } +/* + * The prng_range functions behave like the prng_lg_range, but return a result + * in [0, range) instead of [0, 2**lg_range). + */ + JEMALLOC_ALWAYS_INLINE uint32_t -prng_range_u32(uint32_t *state, uint32_t range, bool atomic) -{ +prng_range_u32(atomic_u32_t *state, uint32_t range, bool atomic) { uint32_t ret; unsigned lg_range; @@ -161,12 +143,11 @@ prng_range_u32(uint32_t *state, uint32_t range, bool atomic) ret = prng_lg_range_u32(state, lg_range, atomic); } while (ret >= range); - return (ret); + return ret; } JEMALLOC_ALWAYS_INLINE uint64_t -prng_range_u64(uint64_t *state, uint64_t range) -{ +prng_range_u64(uint64_t *state, uint64_t range) { uint64_t ret; unsigned lg_range; @@ -180,12 +161,11 @@ prng_range_u64(uint64_t *state, uint64_t range) ret = prng_lg_range_u64(state, lg_range); } while (ret >= range); - return (ret); + return ret; } JEMALLOC_ALWAYS_INLINE size_t -prng_range_zu(size_t *state, size_t range, bool atomic) -{ +prng_range_zu(atomic_zu_t *state, size_t range, bool atomic) { size_t ret; unsigned lg_range; @@ -199,9 +179,7 @@ prng_range_zu(size_t *state, size_t range, bool atomic) ret = prng_lg_range_zu(state, lg_range, atomic); } while (ret >= range); - return (ret); + return ret; } -#endif -#endif /* JEMALLOC_H_INLINES */ -/******************************************************************************/ +#endif /* JEMALLOC_INTERNAL_PRNG_H */ |