summaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
authorjasone <jasone@FreeBSD.org>2007-12-17 01:20:04 +0000
committerjasone <jasone@FreeBSD.org>2007-12-17 01:20:04 +0000
commit65edaae0a7aadfe760209453775c81020f938c03 (patch)
tree1ee1ec80e4587622e81c8bf31e40678154135d8f /lib
parent05daf4f2d42d2c0f7b5cea9461001951281a8ba0 (diff)
downloadFreeBSD-src-65edaae0a7aadfe760209453775c81020f938c03.zip
FreeBSD-src-65edaae0a7aadfe760209453775c81020f938c03.tar.gz
Refactor features a bit in order to make it possible to disable lazy
deallocation and dynamic load balancing via the MALLOC_LAZY_FREE and MALLOC_BALANCE knobs. This is a non-functional change, since these features are still enabled when possible. Clean up a few things that more pedantic compiler settings would cause complaints over.
Diffstat (limited to 'lib')
-rw-r--r--lib/libc/stdlib/malloc.c179
1 files changed, 127 insertions, 52 deletions
diff --git a/lib/libc/stdlib/malloc.c b/lib/libc/stdlib/malloc.c
index fcba9e3..3d1439d 100644
--- a/lib/libc/stdlib/malloc.c
+++ b/lib/libc/stdlib/malloc.c
@@ -104,6 +104,20 @@
# define MALLOC_DEBUG
#endif
+/*
+ * MALLOC_LAZY_FREE enables the use of a per-thread vector of slots that free()
+ * can atomically stuff object pointers into. This can reduce arena lock
+ * contention.
+ */
+#define MALLOC_LAZY_FREE
+
+/*
+ * MALLOC_BALANCE enables monitoring of arena lock contention and dynamically
+ * re-balances arena load if exponentially averaged contention exceeds a
+ * certain threshold.
+ */
+#define MALLOC_BALANCE
+
#include <sys/cdefs.h>
__FBSDID("$FreeBSD$");
@@ -216,6 +230,17 @@ __FBSDID("$FreeBSD$");
# define NO_TLS
#endif
+#ifdef NO_TLS
+ /* MALLOC_BALANCE requires TLS. */
+# ifdef MALLOC_BALANCE
+# undef MALLOC_BALANCE
+# endif
+ /* MALLOC_LAZY_FREE requires TLS. */
+# ifdef MALLOC_LAZY_FREE
+# undef MALLOC_LAZY_FREE
+# endif
+#endif
+
/*
* Size and alignment of memory chunks that are allocated by the OS's virtual
* memory system.
@@ -261,8 +286,9 @@ __FBSDID("$FreeBSD$");
#define RUN_MAX_SMALL_2POW 15
#define RUN_MAX_SMALL (1U << RUN_MAX_SMALL_2POW)
+#ifdef MALLOC_LAZY_FREE
/* Default size of each arena's lazy free cache. */
-#define LAZY_FREE_2POW_DEFAULT 8
+# define LAZY_FREE_2POW_DEFAULT 8
/*
* Number of pseudo-random probes to conduct before considering the cache to be
* overly full. It takes on average n probes to detect fullness of (n-1)/n.
@@ -270,7 +296,8 @@ __FBSDID("$FreeBSD$");
* deallocation is a trial), so the actual average threshold for clearing the
* cache is somewhat lower.
*/
-#define LAZY_FREE_NPROBES 5
+# define LAZY_FREE_NPROBES 5
+#endif
/*
* Hyper-threaded CPUs may need a special instruction inside spin loops in
@@ -295,6 +322,7 @@ __FBSDID("$FreeBSD$");
*/
#define BLOCK_COST_2POW 4
+#ifdef MALLOC_BALANCE
/*
* We use an exponential moving average to track recent lock contention, where
* the size of the history window is N, and alpha=2/(N+1).
@@ -303,13 +331,14 @@ __FBSDID("$FreeBSD$");
* degradation in accuracy, thus making the moving average decay faster than it
* would with precise calculation.
*/
-#define BALANCE_ALPHA_INV_2POW 9
+# define BALANCE_ALPHA_INV_2POW 9
/*
* Threshold value for the exponential moving contention average at which to
* re-assign a thread.
*/
-#define BALANCE_THRESHOLD_DEFAULT (1U << (SPIN_LIMIT_2POW-4))
+# define BALANCE_THRESHOLD_DEFAULT (1U << (SPIN_LIMIT_2POW-4))
+#endif
/******************************************************************************/
@@ -373,7 +402,7 @@ struct arena_stats_s {
uint64_t nmalloc_large;
uint64_t ndalloc_large;
-#ifndef NO_TLS
+#ifdef MALLOC_BALANCE
/* Number of times this arena reassigned a thread due to contention. */
uint64_t nbalance;
#endif
@@ -587,13 +616,15 @@ struct arena_s {
*/
arena_chunk_t *spare;
-#ifndef NO_TLS
+#ifdef MALLOC_BALANCE
/*
* The arena load balancing machinery needs to keep track of how much
* lock contention there is. This value is exponentially averaged.
*/
uint32_t contention;
+#endif
+#ifdef MALLOC_LAZY_FREE
/*
* Deallocation of small objects can be lazy, in which case free_cache
* stores pointers to those objects that have not yet been deallocated.
@@ -734,7 +765,11 @@ static size_t base_mapped;
static arena_t **arenas;
static unsigned narenas;
#ifndef NO_TLS
+# ifdef MALLOC_BALANCE
static unsigned narenas_2pow;
+# else
+static unsigned next_arena;
+# endif
#endif
static pthread_mutex_t arenas_lock; /* Protects arenas initialization. */
@@ -765,8 +800,10 @@ static bool opt_abort = false;
static bool opt_junk = false;
#endif
static bool opt_hint = false;
-#ifndef NO_TLS
+#ifdef MALLOC_LAZY_FREE
static int opt_lazy_free_2pow = LAZY_FREE_2POW_DEFAULT;
+#endif
+#ifdef MALLOC_BALANCE
static uint64_t opt_balance_threshold = BALANCE_THRESHOLD_DEFAULT;
#endif
static bool opt_print_stats = false;
@@ -796,7 +833,7 @@ typedef struct {
* Begin function prototypes for non-inline static functions.
*/
-static void malloc_mutex_init(malloc_mutex_t *a_mutex);
+static void malloc_mutex_init(malloc_mutex_t *mutex);
static bool malloc_spin_init(pthread_mutex_t *lock);
static void wrtmessage(const char *p1, const char *p2, const char *p3,
const char *p4);
@@ -860,27 +897,27 @@ static bool malloc_init_hard(void);
*/
static void
-malloc_mutex_init(malloc_mutex_t *a_mutex)
+malloc_mutex_init(malloc_mutex_t *mutex)
{
static const spinlock_t lock = _SPINLOCK_INITIALIZER;
- a_mutex->lock = lock;
+ mutex->lock = lock;
}
static inline void
-malloc_mutex_lock(malloc_mutex_t *a_mutex)
+malloc_mutex_lock(malloc_mutex_t *mutex)
{
if (__isthreaded)
- _SPINLOCK(&a_mutex->lock);
+ _SPINLOCK(&mutex->lock);
}
static inline void
-malloc_mutex_unlock(malloc_mutex_t *a_mutex)
+malloc_mutex_unlock(malloc_mutex_t *mutex)
{
if (__isthreaded)
- _SPINUNLOCK(&a_mutex->lock);
+ _SPINUNLOCK(&mutex->lock);
}
/*
@@ -1013,7 +1050,7 @@ pow2_ceil(size_t x)
return (x);
}
-#ifndef NO_TLS
+#if (defined(MALLOC_LAZY_FREE) || defined(MALLOC_BALANCE))
/*
* Use a simple linear congruential pseudo-random number generator:
*
@@ -1032,7 +1069,7 @@ pow2_ceil(size_t x)
* the next has a cycle of 4, etc. For this reason, we prefer to use the upper
* bits.
*/
-#define PRN_DEFINE(suffix, var, a, c) \
+# define PRN_DEFINE(suffix, var, a, c) \
static inline void \
sprn_##suffix(uint32_t seed) \
{ \
@@ -1053,21 +1090,25 @@ prn_##suffix(uint32_t lg_range) \
\
return (ret); \
}
-#define SPRN(suffix, seed) sprn_##suffix(seed)
-#define PRN(suffix, lg_range) prn_##suffix(lg_range)
+# define SPRN(suffix, seed) sprn_##suffix(seed)
+# define PRN(suffix, lg_range) prn_##suffix(lg_range)
+#endif
/*
* Define PRNGs, one for each purpose, in order to avoid auto-correlation
* problems.
*/
+#ifdef MALLOC_LAZY_FREE
/* Define the per-thread PRNG used for lazy deallocation. */
static __thread uint32_t lazy_free_x;
PRN_DEFINE(lazy_free, lazy_free_x, 12345, 12347)
+#endif
+#ifdef MALLOC_BALANCE
/* Define the PRNG used for arena assignment. */
static __thread uint32_t balance_x;
-PRN_DEFINE(balance, balance_x, 1297, 1301);
+PRN_DEFINE(balance, balance_x, 1297, 1301)
#endif
static void
@@ -1270,8 +1311,7 @@ base_chunk_node_dealloc(chunk_node_t *node)
static void
stats_print(arena_t *arena)
{
- unsigned i;
- int gap_start;
+ unsigned i, gap_start;
malloc_printf(
" allocated/mapped nmalloc ndalloc\n");
@@ -1289,12 +1329,12 @@ stats_print(arena_t *arena)
malloc_printf("bins: bin size regs pgs requests newruns"
" reruns maxruns curruns\n");
- for (i = 0, gap_start = -1; i < ntbins + nqbins + nsbins; i++) {
+ for (i = 0, gap_start = UINT_MAX; i < ntbins + nqbins + nsbins; i++) {
if (arena->bins[i].stats.nrequests == 0) {
- if (gap_start == -1)
+ if (gap_start == UINT_MAX)
gap_start = i;
} else {
- if (gap_start != -1) {
+ if (gap_start != UINT_MAX) {
if (i > gap_start + 1) {
/* Gap of more than one size class. */
malloc_printf("[%u..%u]\n",
@@ -1303,7 +1343,7 @@ stats_print(arena_t *arena)
/* Gap of one size class. */
malloc_printf("[%u]\n", gap_start);
}
- gap_start = -1;
+ gap_start = UINT_MAX;
}
malloc_printf(
"%13u %1s %4u %4u %3u %9llu %9llu"
@@ -1320,7 +1360,7 @@ stats_print(arena_t *arena)
arena->bins[i].stats.curruns);
}
}
- if (gap_start != -1) {
+ if (gap_start != UINT_MAX) {
if (i > gap_start + 1) {
/* Gap of more than one size class. */
malloc_printf("[%u..%u]\n", gap_start, i - 1);
@@ -1356,7 +1396,7 @@ chunk_comp(chunk_node_t *a, chunk_node_t *b)
}
/* Generate red-black tree code for chunks. */
-RB_GENERATE_STATIC(chunk_tree_s, chunk_node_s, link, chunk_comp);
+RB_GENERATE_STATIC(chunk_tree_s, chunk_node_s, link, chunk_comp)
static void *
pages_map(void *addr, size_t size)
@@ -1754,6 +1794,7 @@ choose_arena_hard(void)
assert(__isthreaded);
+#ifdef MALLOC_LAZY_FREE
/*
* Seed the PRNG used for lazy deallocation. Since seeding only occurs
* on the first allocation by a thread, it is possible for a thread to
@@ -1765,7 +1806,9 @@ choose_arena_hard(void)
* synchronization.
*/
SPRN(lazy_free, (uint32_t)(uintptr_t)(_pthread_self()));
+#endif
+#ifdef MALLOC_BALANCE
/*
* Seed the PRNG used for arena load balancing. We can get away with
* using the same seed here as for the lazy_free PRNG without
@@ -1773,8 +1816,10 @@ choose_arena_hard(void)
* distinct.
*/
SPRN(balance, (uint32_t)(uintptr_t)(_pthread_self()));
+#endif
if (narenas > 1) {
+#ifdef MALLOC_BALANCE
unsigned ind;
ind = PRN(balance, narenas_2pow);
@@ -1784,6 +1829,13 @@ choose_arena_hard(void)
ret = arenas_extend(ind);
malloc_spin_unlock(&arenas_lock);
}
+#else
+ malloc_spin_lock(&arenas_lock);
+ if ((ret = arenas[next_arena]) == NULL)
+ ret = arenas_extend(next_arena);
+ next_arena = (next_arena + 1) % narenas;
+ malloc_spin_unlock(&arenas_lock);
+#endif
} else
ret = arenas[0];
@@ -1809,7 +1861,7 @@ arena_chunk_comp(arena_chunk_t *a, arena_chunk_t *b)
}
/* Generate red-black tree code for arena chunks. */
-RB_GENERATE_STATIC(arena_chunk_tree_s, arena_chunk_s, link, arena_chunk_comp);
+RB_GENERATE_STATIC(arena_chunk_tree_s, arena_chunk_s, link, arena_chunk_comp)
static inline int
arena_run_comp(arena_run_t *a, arena_run_t *b)
@@ -1827,7 +1879,7 @@ arena_run_comp(arena_run_t *a, arena_run_t *b)
}
/* Generate red-black tree code for arena runs. */
-RB_GENERATE_STATIC(arena_run_tree_s, arena_run_s, link, arena_run_comp);
+RB_GENERATE_STATIC(arena_run_tree_s, arena_run_s, link, arena_run_comp)
static inline void *
arena_run_reg_alloc(arena_run_t *run, arena_bin_t *bin)
@@ -2484,10 +2536,10 @@ arena_bin_run_size_calc(arena_bin_t *bin, size_t min_run_size)
return (good_run_size);
}
+#ifdef MALLOC_BALANCE
static inline void
arena_lock_balance(arena_t *arena)
{
-#ifndef NO_TLS
unsigned contention;
contention = malloc_spin_lock(&arena->lock);
@@ -2520,11 +2572,8 @@ arena_lock_balance(arena_t *arena)
}
}
}
-#else
- malloc_spin_lock(&arena->lock);
-#endif
-
}
+#endif
static void *
arena_malloc(arena_t *arena, size_t size, bool zero)
@@ -2569,7 +2618,11 @@ arena_malloc(arena_t *arena, size_t size, bool zero)
}
assert(size == bin->reg_size);
+#ifdef MALLOC_BALANCE
arena_lock_balance(arena);
+#else
+ malloc_spin_lock(&arena->lock);
+#endif
if ((run = bin->runcur) != NULL && run->nfree > 0)
ret = arena_bin_malloc_easy(arena, bin, run);
else
@@ -2597,7 +2650,11 @@ arena_malloc(arena_t *arena, size_t size, bool zero)
} else {
/* Large allocation. */
size = PAGE_CEILING(size);
+#ifdef MALLOC_BALANCE
arena_lock_balance(arena);
+#else
+ malloc_spin_lock(&arena->lock);
+#endif
ret = (void *)arena_run_alloc(arena, size, zero);
if (ret == NULL) {
malloc_spin_unlock(&arena->lock);
@@ -2654,7 +2711,11 @@ arena_palloc(arena_t *arena, size_t alignment, size_t size, size_t alloc_size)
npages = size >> pagesize_2pow;
+#ifdef MALLOC_BALANCE
arena_lock_balance(arena);
+#else
+ malloc_spin_lock(&arena->lock);
+#endif
ret = (void *)arena_run_alloc(arena, alloc_size, false);
if (ret == NULL) {
malloc_spin_unlock(&arena->lock);
@@ -2738,8 +2799,8 @@ arena_salloc(const void *ptr)
chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
pageind = (((uintptr_t)ptr - (uintptr_t)chunk) >> pagesize_2pow);
mapelm = &chunk->map[pageind];
- if (mapelm->pos != 0 || ptr != (void *)((uintptr_t)chunk) + (pageind <<
- pagesize_2pow)) {
+ if (mapelm->pos != 0 || ptr != (void *)(((uintptr_t)chunk) + (pageind <<
+ pagesize_2pow))) {
arena_run_t *run;
pageind -= mapelm->pos;
@@ -2867,7 +2928,7 @@ arena_dalloc_small(arena_t *arena, arena_chunk_t *chunk, void *ptr,
#endif
}
-#ifndef NO_TLS
+#ifdef MALLOC_LAZY_FREE
static inline void
arena_dalloc_lazy(arena_t *arena, arena_chunk_t *chunk, void *ptr,
unsigned pageind, arena_chunk_map_t *mapelm)
@@ -2955,10 +3016,10 @@ arena_dalloc(arena_t *arena, arena_chunk_t *chunk, void *ptr)
pageind = (((uintptr_t)ptr - (uintptr_t)chunk) >> pagesize_2pow);
mapelm = &chunk->map[pageind];
- if (mapelm->pos != 0 || ptr != (void *)((uintptr_t)chunk) + (pageind <<
- pagesize_2pow)) {
+ if (mapelm->pos != 0 || ptr != (void *)(((uintptr_t)chunk) + (pageind <<
+ pagesize_2pow))) {
/* Small allocation. */
-#ifndef NO_TLS
+#ifdef MALLOC_LAZY_FREE
arena_dalloc_lazy(arena, chunk, ptr, pageind, mapelm);
#else
malloc_spin_lock(&arena->lock);
@@ -3004,8 +3065,10 @@ arena_new(arena_t *arena)
RB_INIT(&arena->chunks);
arena->spare = NULL;
-#ifndef NO_TLS
+#ifdef MALLOC_BALANCE
arena->contention = 0;
+#endif
+#ifdef MALLOC_LAZY_FREE
if (opt_lazy_free_2pow >= 0) {
arena->free_cache = (void **) base_alloc(sizeof(void *)
* (1U << opt_lazy_free_2pow));
@@ -3529,12 +3592,14 @@ malloc_print_stats(void)
_malloc_message("CPUs: ", umax2s(ncpus, s), "\n", "");
_malloc_message("Max arenas: ", umax2s(narenas, s), "\n", "");
-#ifndef NO_TLS
+#ifdef MALLOC_LAZY_FREE
if (opt_lazy_free_2pow >= 0) {
_malloc_message("Lazy free slots: ",
umax2s(1U << opt_lazy_free_2pow, s), "\n", "");
} else
_malloc_message("Lazy free slots: 0\n", "", "", "");
+#endif
+#ifdef MALLOC_BALANCE
_malloc_message("Arena balance threshold: ",
umax2s(opt_balance_threshold, s), "\n", "");
#endif
@@ -3550,7 +3615,7 @@ malloc_print_stats(void)
#ifdef MALLOC_STATS
{
size_t allocated, mapped;
-#ifndef NO_TLS
+#ifdef MALLOC_BALANCE
uint64_t nbalance = 0;
#endif
unsigned i;
@@ -3566,7 +3631,7 @@ malloc_print_stats(void)
arenas[i]->stats.allocated_small;
allocated +=
arenas[i]->stats.allocated_large;
-#ifndef NO_TLS
+#ifdef MALLOC_BALANCE
nbalance += arenas[i]->stats.nbalance;
#endif
malloc_spin_unlock(&arenas[i]->lock);
@@ -3586,7 +3651,7 @@ malloc_print_stats(void)
malloc_printf("Allocated: %zu, mapped: %zu\n",
allocated, mapped);
-#ifndef NO_TLS
+#ifdef MALLOC_BALANCE
malloc_printf("Arena balance reassignments: %llu\n",
nbalance);
#endif
@@ -3677,7 +3742,7 @@ malloc_init_hard(void)
}
}
-#ifndef NO_TLS
+#ifdef MALLOC_LAZY_FREE
if (ncpus == 1)
opt_lazy_free_2pow = -1;
#endif
@@ -3757,12 +3822,12 @@ malloc_init_hard(void)
opt_abort = true;
break;
case 'b':
-#ifndef NO_TLS
+#ifdef MALLOC_BALANCE
opt_balance_threshold >>= 1;
#endif
break;
case 'B':
-#ifndef NO_TLS
+#ifdef MALLOC_BALANCE
if (opt_balance_threshold == 0)
opt_balance_threshold = 1;
else if ((opt_balance_threshold << 1)
@@ -3803,13 +3868,13 @@ malloc_init_hard(void)
opt_chunk_2pow++;
break;
case 'l':
-#ifndef NO_TLS
+#ifdef MALLOC_LAZY_FREE
if (opt_lazy_free_2pow >= 0)
opt_lazy_free_2pow--;
#endif
break;
case 'L':
-#ifndef NO_TLS
+#ifdef MALLOC_LAZY_FREE
if (ncpus > 1)
opt_lazy_free_2pow++;
#endif
@@ -3922,7 +3987,7 @@ malloc_init_hard(void)
}
arena_maxclass = chunksize - (arena_chunk_header_npages <<
pagesize_2pow);
-#ifndef NO_TLS
+#ifdef MALLOC_LAZY_FREE
/*
* Make sure that allocating the free_cache does not exceed the limits
* of what base_alloc() can handle.
@@ -4000,7 +4065,7 @@ malloc_init_hard(void)
if (narenas == 0)
narenas = 1;
}
-#ifndef NO_TLS
+#ifdef MALLOC_BALANCE
assert(narenas != 0);
for (narenas_2pow = 0;
(narenas >> (narenas_2pow + 1)) != 0;
@@ -4034,6 +4099,12 @@ malloc_init_hard(void)
}
#endif
+#ifndef NO_TLS
+# ifndef MALLOC_BALANCE
+ next_arena = 0;
+# endif
+#endif
+
/* Allocate and initialize arenas. */
arenas = (arena_t **)base_alloc(sizeof(arena_t *) * narenas);
if (arenas == NULL) {
@@ -4062,11 +4133,15 @@ malloc_init_hard(void)
* threaded mode.
*/
arenas_map = arenas[0];
+#endif
/*
* Seed here for the initial thread, since choose_arena_hard() is only
* called for other threads. The seed values don't really matter.
*/
+#ifdef MALLOC_LAZY_FREE
SPRN(lazy_free, 42);
+#endif
+#ifdef MALLOC_BALANCE
SPRN(balance, 42);
#endif
OpenPOWER on IntegriCloud