summaryrefslogtreecommitdiffstats
path: root/include/jemalloc/internal
diff options
context:
space:
mode:
Diffstat (limited to 'include/jemalloc/internal')
-rw-r--r--include/jemalloc/internal/arena.h2
-rw-r--r--include/jemalloc/internal/atomic.h18
-rw-r--r--include/jemalloc/internal/private_symbols.txt11
-rw-r--r--include/jemalloc/internal/prng.h150
4 files changed, 159 insertions, 22 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/atomic.h b/include/jemalloc/internal/atomic.h
index 3936f68..3f15ea1 100644
--- a/include/jemalloc/internal/atomic.h
+++ b/include/jemalloc/internal/atomic.h
@@ -66,7 +66,8 @@ void atomic_write_u(unsigned *p, unsigned x);
#if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_ATOMIC_C_))
/******************************************************************************/
/* 64-bit operations. */
-#if (defined(__amd64__) || defined(__x86_64__))
+#if (LG_SIZEOF_PTR == 3 || LG_SIZEOF_INT == 3)
+# if (defined(__amd64__) || defined(__x86_64__))
JEMALLOC_INLINE uint64_t
atomic_add_uint64(uint64_t *p, uint64_t x)
{
@@ -124,7 +125,7 @@ atomic_write_uint64(uint64_t *p, uint64_t x)
: "memory" /* Clobbers. */
);
}
-#elif (defined(JEMALLOC_C11ATOMICS))
+# elif (defined(JEMALLOC_C11ATOMICS))
JEMALLOC_INLINE uint64_t
atomic_add_uint64(uint64_t *p, uint64_t x)
{
@@ -152,7 +153,7 @@ atomic_write_uint64(uint64_t *p, uint64_t x)
volatile atomic_uint_least64_t *a = (volatile atomic_uint_least64_t *)p;
atomic_store(a, x);
}
-#elif (defined(JEMALLOC_ATOMIC9))
+# elif (defined(JEMALLOC_ATOMIC9))
JEMALLOC_INLINE uint64_t
atomic_add_uint64(uint64_t *p, uint64_t x)
{
@@ -192,7 +193,7 @@ atomic_write_uint64(uint64_t *p, uint64_t x)
atomic_store_rel_long(p, x);
}
-#elif (defined(JEMALLOC_OSATOMIC))
+# elif (defined(JEMALLOC_OSATOMIC))
JEMALLOC_INLINE uint64_t
atomic_add_uint64(uint64_t *p, uint64_t x)
{
@@ -224,7 +225,7 @@ atomic_write_uint64(uint64_t *p, uint64_t x)
o = atomic_read_uint64(p);
} while (atomic_cas_uint64(p, o, x));
}
-#elif (defined(_MSC_VER))
+# elif (defined(_MSC_VER))
JEMALLOC_INLINE uint64_t
atomic_add_uint64(uint64_t *p, uint64_t x)
{
@@ -254,7 +255,7 @@ atomic_write_uint64(uint64_t *p, uint64_t x)
InterlockedExchange64(p, x);
}
-#elif (defined(__GCC_HAVE_SYNC_COMPARE_AND_SWAP_8) || \
+# elif (defined(__GCC_HAVE_SYNC_COMPARE_AND_SWAP_8) || \
defined(JE_FORCE_SYNC_COMPARE_AND_SWAP_8))
JEMALLOC_INLINE uint64_t
atomic_add_uint64(uint64_t *p, uint64_t x)
@@ -283,8 +284,9 @@ atomic_write_uint64(uint64_t *p, uint64_t x)
__sync_lock_test_and_set(p, x);
}
-#else
-# error "Missing implementation for 64-bit atomic operations"
+# else
+# error "Missing implementation for 64-bit atomic operations"
+# endif
#endif
/******************************************************************************/
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);
generated by cgit v0.12 at 2025-12-29 20:41:49 (GMT)