diff options
author | Jason Evans <jasone@canonware.com> | 2016-11-07 10:52:44 -0800 |
---|---|---|
committer | Jason Evans <jasone@canonware.com> | 2016-11-07 11:50:59 -0800 |
commit | 5d6cb6eb66b05261cccd2b416f50ad98d1735229 (patch) | |
tree | af4c95ab6f502a005a2da7b7a1e9099604b1ceb1 /include | |
parent | a4e83e859353ea19dc8377088eae31520d291550 (diff) | |
download | jemalloc-5d6cb6eb66b05261cccd2b416f50ad98d1735229.tar.gz |
Refactor prng to not use 64-bit atomics on 32-bit platforms.
This resolves #495.
Diffstat (limited to 'include')
-rw-r--r-- | include/jemalloc/internal/arena.h | 2 | ||||
-rw-r--r-- | include/jemalloc/internal/private_symbols.txt | 11 | ||||
-rw-r--r-- | include/jemalloc/internal/prng.h | 150 |
3 files changed, 149 insertions, 14 deletions
diff --git a/include/jemalloc/internal/arena.h b/include/jemalloc/internal/arena.h index 1277d08..f39ce54 100644 --- a/include/jemalloc/internal/arena.h +++ b/include/jemalloc/internal/arena.h @@ -370,7 +370,7 @@ struct arena_s { * PRNG state for cache index randomization of large allocation base * pointers. */ - uint64_t offset_state; + size_t offset_state; dss_prec_t dss_prec; diff --git a/include/jemalloc/internal/private_symbols.txt b/include/jemalloc/internal/private_symbols.txt index 8972b37..87c8c9b 100644 --- a/include/jemalloc/internal/private_symbols.txt +++ b/include/jemalloc/internal/private_symbols.txt @@ -405,8 +405,15 @@ pind2sz_tab pow2_ceil_u32 pow2_ceil_u64 pow2_ceil_zu -prng_lg_range -prng_range +prng_lg_range_u32 +prng_lg_range_u64 +prng_lg_range_zu +prng_range_u32 +prng_range_u64 +prng_range_zu +prng_state_next_u32 +prng_state_next_u64 +prng_state_next_zu prof_active prof_active_get prof_active_get_unlocked diff --git a/include/jemalloc/internal/prng.h b/include/jemalloc/internal/prng.h index 5830f8b..c2bda19 100644 --- a/include/jemalloc/internal/prng.h +++ b/include/jemalloc/internal/prng.h @@ -19,8 +19,12 @@ * the next has a cycle of 4, etc. For this reason, we prefer to use the upper * bits. */ -#define PRNG_A UINT64_C(6364136223846793005) -#define PRNG_C UINT64_C(1442695040888963407) + +#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 */ /******************************************************************************/ @@ -35,28 +39,133 @@ #ifdef JEMALLOC_H_INLINES #ifndef JEMALLOC_ENABLE_INLINE -uint64_t prng_lg_range(uint64_t *state, unsigned lg_range); -uint64_t prng_range(uint64_t *state, uint64_t range); +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); + +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); +} + JEMALLOC_ALWAYS_INLINE uint64_t -prng_lg_range(uint64_t *state, unsigned lg_range) +prng_state_next_u64(uint64_t state) { - uint64_t ret; + + return ((state * PRNG_A_64) + PRNG_C_64); +} + +JEMALLOC_ALWAYS_INLINE size_t +prng_state_next_zu(size_t state) +{ + +#if LG_SIZEOF_PTR == 2 + return ((state * PRNG_A_32) + PRNG_C_32); +#elif LG_SIZEOF_PTR == 3 + return ((state * PRNG_A_64) + PRNG_C_64); +#else +#error Unsupported pointer size +#endif +} + +JEMALLOC_ALWAYS_INLINE uint32_t +prng_lg_range_u32(uint32_t *state, unsigned lg_range, bool atomic) +{ + uint32_t ret, state1; + + assert(lg_range > 0); + assert(lg_range <= 32); + + if (atomic) { + uint32_t state0; + + do { + state0 = atomic_read_uint32(state); + state1 = prng_state_next_u32(state0); + } while (atomic_cas_uint32(state, state0, state1)); + } else { + state1 = prng_state_next_u32(*state); + *state = state1; + } + ret = state1 >> (32 - lg_range); + + 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) +{ + uint64_t ret, state1; assert(lg_range > 0); assert(lg_range <= 64); - ret = (*state * PRNG_A) + PRNG_C; - *state = ret; - ret >>= (64 - lg_range); + state1 = prng_state_next_u64(*state); + *state = state1; + ret = state1 >> (64 - lg_range); + + return (ret); +} + +JEMALLOC_ALWAYS_INLINE size_t +prng_lg_range_zu(size_t *state, unsigned lg_range, bool atomic) +{ + size_t ret, state1; + + assert(lg_range > 0); + assert(lg_range <= ZU(1) << (3 + LG_SIZEOF_PTR)); + + if (atomic) { + size_t state0; + + do { + state0 = atomic_read_z(state); + state1 = prng_state_next_zu(state0); + } while (atomic_cas_z(state, state0, state1)); + } else { + state1 = prng_state_next_zu(*state); + *state = state1; + } + ret = state1 >> ((ZU(1) << (3 + LG_SIZEOF_PTR)) - lg_range); + + return (ret); +} + +JEMALLOC_ALWAYS_INLINE uint32_t +prng_range_u32(uint32_t *state, uint32_t range, bool atomic) +{ + uint32_t ret; + unsigned lg_range; + + assert(range > 1); + + /* Compute the ceiling of lg(range). */ + lg_range = ffs_u32(pow2_ceil_u32(range)) - 1; + + /* Generate a result in [0..range) via repeated trial. */ + do { + ret = prng_lg_range_u32(state, lg_range, atomic); + } while (ret >= range); return (ret); } JEMALLOC_ALWAYS_INLINE uint64_t -prng_range(uint64_t *state, uint64_t range) +prng_range_u64(uint64_t *state, uint64_t range) { uint64_t ret; unsigned lg_range; @@ -68,7 +177,26 @@ prng_range(uint64_t *state, uint64_t range) /* Generate a result in [0..range) via repeated trial. */ do { - ret = prng_lg_range(state, lg_range); + ret = prng_lg_range_u64(state, lg_range); + } while (ret >= range); + + return (ret); +} + +JEMALLOC_ALWAYS_INLINE size_t +prng_range_zu(size_t *state, size_t range, bool atomic) +{ + size_t ret; + unsigned lg_range; + + assert(range > 1); + + /* Compute the ceiling of lg(range). */ + lg_range = ffs_u64(pow2_ceil_u64(range)) - 1; + + /* Generate a result in [0..range) via repeated trial. */ + do { + ret = prng_lg_range_zu(state, lg_range, atomic); } while (ret >= range); return (ret); |