PERFORCE change 148631 for review
Ed Schouten
ed at FreeBSD.org
Wed Aug 27 17:09:43 UTC 2008
http://perforce.freebsd.org/chv.cgi?CH=148631
Change 148631 by ed at ed_dull on 2008/08/27 17:09:16
IFC.
Affected files ...
.. //depot/projects/mpsafetty/lib/libc/include/libc_private.h#2 integrate
.. //depot/projects/mpsafetty/lib/libc/stdlib/Symbol.map#3 integrate
.. //depot/projects/mpsafetty/lib/libc/stdlib/malloc.3#2 integrate
.. //depot/projects/mpsafetty/lib/libc/stdlib/malloc.c#5 integrate
.. //depot/projects/mpsafetty/lib/libc/sys/execve.2#2 integrate
.. //depot/projects/mpsafetty/lib/libc/sys/wait.2#2 integrate
.. //depot/projects/mpsafetty/lib/libthr/thread/thr_exit.c#2 integrate
.. //depot/projects/mpsafetty/sbin/ifconfig/ifconfig.8#5 integrate
.. //depot/projects/mpsafetty/sbin/ipfw/ipfw.8#4 integrate
.. //depot/projects/mpsafetty/sbin/ping6/ping6.8#2 integrate
.. //depot/projects/mpsafetty/sbin/ping6/ping6.c#2 integrate
.. //depot/projects/mpsafetty/share/man/man4/wi.4#4 integrate
.. //depot/projects/mpsafetty/sys/amd64/amd64/bpf_jit_machdep.c#6 integrate
.. //depot/projects/mpsafetty/sys/boot/forth/loader.conf#5 integrate
.. //depot/projects/mpsafetty/sys/conf/files.mips#2 integrate
.. //depot/projects/mpsafetty/sys/conf/files.powerpc#2 integrate
.. //depot/projects/mpsafetty/sys/conf/options#10 integrate
.. //depot/projects/mpsafetty/sys/dev/ex/if_ex_pccard.c#2 integrate
.. //depot/projects/mpsafetty/sys/dev/pccard/pccard_cis.c#2 integrate
.. //depot/projects/mpsafetty/sys/dev/pccard/pccarddevs#4 integrate
.. //depot/projects/mpsafetty/sys/dev/tsec/if_tsec.c#2 integrate
.. //depot/projects/mpsafetty/sys/dev/tsec/if_tsec.h#2 integrate
.. //depot/projects/mpsafetty/sys/dev/tsec/if_tsec_ocp.c#1 branch
.. //depot/projects/mpsafetty/sys/dev/wi/if_wi_pccard.c#3 integrate
.. //depot/projects/mpsafetty/sys/i386/cpufreq/est.c#4 integrate
.. //depot/projects/mpsafetty/sys/i386/i386/bpf_jit_machdep.c#6 integrate
.. //depot/projects/mpsafetty/sys/kern/imgact_shell.c#2 integrate
.. //depot/projects/mpsafetty/sys/kern/kern_exit.c#4 integrate
.. //depot/projects/mpsafetty/sys/kern/tty.c#33 edit
.. //depot/projects/mpsafetty/sys/kern/tty_pts.c#16 edit
.. //depot/projects/mpsafetty/sys/modules/wi/Makefile#2 integrate
.. //depot/projects/mpsafetty/sys/net/bpf.h#3 integrate
.. //depot/projects/mpsafetty/sys/net/bpf_jitter.c#4 integrate
.. //depot/projects/mpsafetty/sys/netinet/sctp_pcb.c#5 integrate
.. //depot/projects/mpsafetty/sys/powerpc/booke/locore.S#2 integrate
.. //depot/projects/mpsafetty/sys/powerpc/booke/machdep.c#2 integrate
.. //depot/projects/mpsafetty/sys/powerpc/booke/pmap.c#2 integrate
.. //depot/projects/mpsafetty/sys/sys/ttydevsw.h#5 edit
.. //depot/projects/mpsafetty/sys/sys/wait.h#2 integrate
.. //depot/projects/mpsafetty/tools/regression/bpf/bpf_filter/Makefile#3 integrate
.. //depot/projects/mpsafetty/tools/regression/bpf/bpf_filter/bpf_test.c#3 integrate
.. //depot/projects/mpsafetty/tools/regression/bpf/bpf_filter/tests/test0001.h#2 integrate
.. //depot/projects/mpsafetty/tools/regression/bpf/bpf_filter/tests/test0075.h#1 branch
.. //depot/projects/mpsafetty/tools/regression/bpf/bpf_filter/tests/test0076.h#1 branch
.. //depot/projects/mpsafetty/tools/regression/bpf/bpf_filter/tests/test0077.h#1 branch
.. //depot/projects/mpsafetty/tools/regression/bpf/bpf_filter/tests/test0078.h#1 branch
.. //depot/projects/mpsafetty/tools/regression/bpf/bpf_filter/tests/test0079.h#1 branch
.. //depot/projects/mpsafetty/usr.bin/netstat/inet.c#3 integrate
Differences ...
==== //depot/projects/mpsafetty/lib/libc/include/libc_private.h#2 (text+ko) ====
@@ -26,7 +26,7 @@
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*
- * $FreeBSD: src/lib/libc/include/libc_private.h,v 1.19 2008/06/23 05:22:06 ed Exp $
+ * $FreeBSD: src/lib/libc/include/libc_private.h,v 1.20 2008/08/27 02:00:53 jasone Exp $
*
* Private definitions for libc, libc_r and libpthread.
*
@@ -158,6 +158,12 @@
extern const char *__progname;
/*
+ * This function is used by the threading libraries to notify malloc that a
+ * thread is exiting.
+ */
+void _malloc_thread_cleanup(void);
+
+/*
* These functions are used by the threading libraries in order to protect
* malloc across fork().
*/
==== //depot/projects/mpsafetty/lib/libc/stdlib/Symbol.map#3 (text) ====
@@ -1,5 +1,5 @@
/*
- * $FreeBSD: src/lib/libc/stdlib/Symbol.map,v 1.8 2008/08/20 08:31:58 ed Exp $
+ * $FreeBSD: src/lib/libc/stdlib/Symbol.map,v 1.9 2008/08/27 02:00:53 jasone Exp $
*/
FBSD_1.0 {
@@ -93,6 +93,7 @@
};
FBSDprivate_1.0 {
+ _malloc_thread_cleanup;
_malloc_prefork;
_malloc_postfork;
__system;
==== //depot/projects/mpsafetty/lib/libc/stdlib/malloc.3#2 (text+ko) ====
@@ -30,9 +30,9 @@
.\" SUCH DAMAGE.
.\"
.\" @(#)malloc.3 8.1 (Berkeley) 6/4/93
-.\" $FreeBSD: src/lib/libc/stdlib/malloc.3,v 1.78 2008/02/17 17:09:24 jasone Exp $
+.\" $FreeBSD: src/lib/libc/stdlib/malloc.3,v 1.79 2008/08/27 02:00:53 jasone Exp $
.\"
-.Dd February 17, 2008
+.Dd August 26, 2008
.Dt MALLOC 3
.Os
.Sh NAME
@@ -154,7 +154,7 @@
implementation-dependent.
.Sh TUNING
Once, when the first call is made to one of these memory allocation
-routines, various flags will be set or reset, which affect the
+routines, various flags will be set or reset, which affects the
workings of this allocator implementation.
.Pp
The
@@ -196,6 +196,11 @@
Therefore, some applications may benefit from increasing or decreasing this
threshold parameter.
This option is not available for some configurations (non-PIC).
+.It C
+Double/halve the size of the maximum size class that is a multiple of the
+cacheline size (64).
+Above this size, subpage spacing (256 bytes) is used for size classes.
+The default value is 512 bytes.
.It D
Use
.Xr sbrk 2
@@ -214,6 +219,16 @@
The default is 512 pages per arena;
.Ev MALLOC_OPTIONS=10f
will prevent any dirty unused pages from accumulating.
+.It G
+When there are multiple threads, use thread-specific caching for objects that
+are smaller than one page.
+This option is enabled by default.
+Thread-specific caching allows many allocations to be satisfied without
+performing any thread synchronization, at the cost of increased memory use.
+See the
+.Dq R
+option for related tuning information.
+This option is not available for some configurations (non-PIC).
.It J
Each byte of new memory allocated by
.Fn malloc ,
@@ -248,7 +263,7 @@
acquiring memory.
.It N
Double/halve the number of arenas.
-The default number of arenas is four times the number of CPUs, or one if there
+The default number of arenas is two times the number of CPUs, or one if there
is a single CPU.
.It P
Various statistics are printed at program exit via an
@@ -259,14 +274,18 @@
Therefore, this option should only be used with care; it is primarily intended
as a performance tuning aid during application development.
.It Q
-Double/halve the size of the allocation quantum.
-The default quantum is the minimum allowed by the architecture (typically 8 or
-16 bytes).
-.It S
Double/halve the size of the maximum size class that is a multiple of the
-quantum.
-Above this size, power-of-two spacing is used for size classes.
-The default value is 512 bytes.
+quantum (8 or 16 bytes, depending on architecture).
+Above this size, cacheline spacing is used for size classes.
+The default value is 128 bytes.
+.It R
+Double/halve magazine size, which approximately doubles/halves the number of
+rounds in each magazine.
+Magazines are used by the thread-specific caching machinery to acquire and
+release objects in bulk.
+Increasing the magazine size decreases locking overhead, at the expense of
+increased memory usage.
+This option is not available for some configurations (non-PIC).
.It U
Generate
.Dq utrace
@@ -358,6 +377,13 @@
However, it may make sense to reduce the number of arenas if an application
does not make much use of the allocation functions.
.Pp
+In addition to multiple arenas, this allocator supports thread-specific
+caching for small objects (smaller than one page), in order to make it
+possible to completely avoid synchronization for most small allocation requests.
+Such caching allows very fast allocation in the common case, but it increases
+memory usage and fragmentation, since a bounded number of objects can remain
+allocated in each thread cache.
+.Pp
Memory is conceptually broken into equal-sized chunks, where the chunk size is
a power of two that is greater than the page size.
Chunks are always aligned to multiples of the chunk size.
@@ -366,7 +392,7 @@
.Pp
User objects are broken into three categories according to size: small, large,
and huge.
-Small objects are no larger than one half of a page.
+Small objects are smaller than one page.
Large objects are smaller than the chunk size.
Huge objects are a multiple of the chunk size.
Small and large objects are managed by arenas; huge objects are managed
@@ -378,23 +404,24 @@
contiguous pages (unused, backing a set of small objects, or backing one large
object).
The combination of chunk alignment and chunk page maps makes it possible to
-determine all metadata regarding small and large allocations in
-constant and logarithmic time, respectively.
+determine all metadata regarding small and large allocations in constant time.
.Pp
Small objects are managed in groups by page runs.
Each run maintains a bitmap that tracks which regions are in use.
-Allocation requests that are no more than half the quantum (see the
+Allocation requests that are no more than half the quantum (8 or 16, depending
+on architecture) are rounded up to the nearest power of two.
+Allocation requests that are more than half the quantum, but no more than the
+minimum cacheline-multiple size class (see the
.Dq Q
-option) are rounded up to the nearest power of two (typically 2, 4, or 8).
-Allocation requests that are more than half the quantum, but no more than the
-maximum quantum-multiple size class (see the
-.Dq S
option) are rounded up to the nearest multiple of the quantum.
-Allocation requests that are larger than the maximum quantum-multiple size
-class, but no larger than one half of a page, are rounded up to the nearest
-power of two.
-Allocation requests that are larger than half of a page, but small enough to
-fit in an arena-managed chunk (see the
+Allocation requests that are more than the minumum cacheline-multiple size
+class, but no more than the minimum subpage-multiple size class (see the
+.Dq C
+option) are rounded up to the nearest multiple of the cacheline size (64).
+Allocation requests that are more than the minimum subpage-multiple size class
+are rounded up to the nearest multiple of the subpage size (256).
+Allocation requests that are more than one page, but small enough to fit in
+an arena-managed chunk (see the
.Dq K
option), are rounded up to the nearest run size.
Allocation requests that are too large to fit in an arena-managed chunk are
@@ -402,8 +429,8 @@
.Pp
Allocations are packed tightly together, which can be an issue for
multi-threaded applications.
-If you need to assure that allocations do not suffer from cache line sharing,
-round your allocation requests up to the nearest multiple of the cache line
+If you need to assure that allocations do not suffer from cacheline sharing,
+round your allocation requests up to the nearest multiple of the cacheline
size.
.Sh DEBUGGING MALLOC PROBLEMS
The first thing to do is to set the
==== //depot/projects/mpsafetty/lib/libc/stdlib/malloc.c#5 (text+ko) ====
@@ -35,6 +35,9 @@
* + Multiple arenas are used if there are multiple CPUs, which reduces lock
* contention and cache sloshing.
*
+ * + Thread-specific caching is used if there are multiple threads, which
+ * reduces the amount of locking.
+ *
* + Cache line sharing between arenas is avoided for internal data
* structures.
*
@@ -48,37 +51,49 @@
* and a 16 byte quantum on a 32-bit system, the size classes in each category
* are as follows:
*
- * |=====================================|
- * | Category | Subcategory | Size |
- * |=====================================|
- * | Small | Tiny | 2 |
- * | | | 4 |
- * | | | 8 |
- * | |----------------+---------|
- * | | Quantum-spaced | 16 |
- * | | | 32 |
- * | | | 48 |
- * | | | ... |
- * | | | 480 |
- * | | | 496 |
- * | | | 512 |
- * | |----------------+---------|
- * | | Sub-page | 1 kB |
- * | | | 2 kB |
- * |=====================================|
- * | Large | 4 kB |
- * | | 8 kB |
- * | | 12 kB |
- * | | ... |
- * | | 1012 kB |
- * | | 1016 kB |
- * | | 1020 kB |
- * |=====================================|
- * | Huge | 1 MB |
- * | | 2 MB |
- * | | 3 MB |
- * | | ... |
- * |=====================================|
+ * |=======================================|
+ * | Category | Subcategory | Size |
+ * |=======================================|
+ * | Small | Tiny | 2 |
+ * | | | 4 |
+ * | | | 8 |
+ * | |------------------+---------|
+ * | | Quantum-spaced | 16 |
+ * | | | 32 |
+ * | | | 48 |
+ * | | | ... |
+ * | | | 96 |
+ * | | | 112 |
+ * | | | 128 |
+ * | |------------------+---------|
+ * | | Cacheline-spaced | 192 |
+ * | | | 256 |
+ * | | | 320 |
+ * | | | 384 |
+ * | | | 448 |
+ * | | | 512 |
+ * | |------------------+---------|
+ * | | Sub-page | 760 |
+ * | | | 1024 |
+ * | | | 1280 |
+ * | | | ... |
+ * | | | 3328 |
+ * | | | 3584 |
+ * | | | 3840 |
+ * |=======================================|
+ * | Large | 4 kB |
+ * | | 8 kB |
+ * | | 12 kB |
+ * | | ... |
+ * | | 1012 kB |
+ * | | 1016 kB |
+ * | | 1020 kB |
+ * |=======================================|
+ * | Huge | 1 MB |
+ * | | 2 MB |
+ * | | 3 MB |
+ * | | ... |
+ * |=======================================|
*
* A different mechanism is used for each category:
*
@@ -113,6 +128,19 @@
#endif
/*
+ * MALLOC_TINY enables support for tiny objects, which are smaller than one
+ * quantum.
+ */
+#define MALLOC_TINY
+
+/*
+ * MALLOC_MAG enables a magazine-based thread-specific caching layer for small
+ * objects. This makes it possible to allocate/deallocate objects without any
+ * locking when the cache is in the steady state.
+ */
+#define MALLOC_MAG
+
+/*
* MALLOC_BALANCE enables monitoring of arena lock contention and dynamically
* re-balances arena load if exponentially averaged contention exceeds a
* certain threshold.
@@ -128,7 +156,7 @@
#define MALLOC_DSS
#include <sys/cdefs.h>
-__FBSDID("$FreeBSD: src/lib/libc/stdlib/malloc.c,v 1.176 2008/08/14 17:31:42 jasone Exp $");
+__FBSDID("$FreeBSD: src/lib/libc/stdlib/malloc.c,v 1.177 2008/08/27 02:00:53 jasone Exp $");
#include "libc_private.h"
#ifdef MALLOC_DEBUG
@@ -184,46 +212,63 @@
/* Size of stack-allocated buffer passed to strerror_r(). */
#define STRERROR_BUF 64
-/* Minimum alignment of allocations is 2^QUANTUM_2POW_MIN bytes. */
+/*
+ * The const_size2bin table is sized according to PAGESIZE_2POW, but for
+ * correctness reasons, we never assume that
+ * (pagesize == (1U << * PAGESIZE_2POW)).
+ *
+ * Minimum alignment of allocations is 2^QUANTUM_2POW bytes.
+ */
#ifdef __i386__
-# define QUANTUM_2POW_MIN 4
+# define PAGESIZE_2POW 12
+# define QUANTUM_2POW 4
# define SIZEOF_PTR_2POW 2
# define CPU_SPINWAIT __asm__ volatile("pause")
#endif
#ifdef __ia64__
-# define QUANTUM_2POW_MIN 4
+# define PAGESIZE_2POW 12
+# define QUANTUM_2POW 4
# define SIZEOF_PTR_2POW 3
#endif
#ifdef __alpha__
-# define QUANTUM_2POW_MIN 4
+# define PAGESIZE_2POW 13
+# define QUANTUM_2POW 4
# define SIZEOF_PTR_2POW 3
# define NO_TLS
#endif
#ifdef __sparc64__
-# define QUANTUM_2POW_MIN 4
+# define PAGESIZE_2POW 13
+# define QUANTUM_2POW 4
# define SIZEOF_PTR_2POW 3
# define NO_TLS
#endif
#ifdef __amd64__
-# define QUANTUM_2POW_MIN 4
+# define PAGESIZE_2POW 12
+# define QUANTUM_2POW 4
# define SIZEOF_PTR_2POW 3
# define CPU_SPINWAIT __asm__ volatile("pause")
#endif
#ifdef __arm__
-# define QUANTUM_2POW_MIN 3
+# define PAGESIZE_2POW 12
+# define QUANTUM_2POW 3
# define SIZEOF_PTR_2POW 2
# define NO_TLS
#endif
#ifdef __mips__
-# define QUANTUM_2POW_MIN 3
+# define PAGESIZE_2POW 12
+# define QUANTUM_2POW 3
# define SIZEOF_PTR_2POW 2
# define NO_TLS
#endif
#ifdef __powerpc__
-# define QUANTUM_2POW_MIN 4
+# define PAGESIZE_2POW 12
+# define QUANTUM_2POW 4
# define SIZEOF_PTR_2POW 2
#endif
+#define QUANTUM ((size_t)(1U << QUANTUM_2POW))
+#define QUANTUM_MASK (QUANTUM - 1)
+
#define SIZEOF_PTR (1U << SIZEOF_PTR_2POW)
/* sizeof(int) == (1U << SIZEOF_INT_2POW). */
@@ -237,6 +282,10 @@
#endif
#ifdef NO_TLS
+ /* MALLOC_MAG requires TLS. */
+# ifdef MALLOC_MAG
+# undef MALLOC_MAG
+# endif
/* MALLOC_BALANCE requires TLS. */
# ifdef MALLOC_BALANCE
# undef MALLOC_BALANCE
@@ -253,23 +302,42 @@
#define DIRTY_MAX_DEFAULT (1U << 9)
/*
- * Maximum size of L1 cache line. This is used to avoid cache line aliasing,
- * so over-estimates are okay (up to a point), but under-estimates will
- * negatively affect performance.
+ * Maximum size of L1 cache line. This is used to avoid cache line aliasing.
+ * In addition, this controls the spacing of cacheline-spaced size classes.
*/
#define CACHELINE_2POW 6
#define CACHELINE ((size_t)(1U << CACHELINE_2POW))
+#define CACHELINE_MASK (CACHELINE - 1)
-/* Smallest size class to support. */
-#define TINY_MIN_2POW 1
+/*
+ * Subpages are an artificially designated partitioning of pages. Their only
+ * purpose is to support subpage-spaced size classes.
+ *
+ * There must be at least 4 subpages per page, due to the way size classes are
+ * handled.
+ */
+#define SUBPAGE_2POW 8
+#define SUBPAGE ((size_t)(1U << SUBPAGE_2POW))
+#define SUBPAGE_MASK (SUBPAGE - 1)
+
+#ifdef MALLOC_TINY
+ /* Smallest size class to support. */
+# define TINY_MIN_2POW 1
+#endif
/*
* Maximum size class that is a multiple of the quantum, but not (necessarily)
* a power of 2. Above this size, allocations are rounded up to the nearest
* power of 2.
*/
-#define SMALL_MAX_2POW_DEFAULT 9
-#define SMALL_MAX_DEFAULT (1U << SMALL_MAX_2POW_DEFAULT)
+#define QSPACE_MAX_2POW_DEFAULT 7
+
+/*
+ * Maximum size class that is a multiple of the cacheline, but not (necessarily)
+ * a power of 2. Above this size, allocations are rounded up to the nearest
+ * power of 2.
+ */
+#define CSPACE_MAX_2POW_DEFAULT 9
/*
* RUN_MAX_OVRHD indicates maximum desired run header overhead. Runs are sized
@@ -293,8 +361,7 @@
#define RUN_MAX_OVRHD_RELAX 0x00001800U
/* Put a cap on small object run size. This overrides RUN_MAX_OVRHD. */
-#define RUN_MAX_SMALL_2POW 15
-#define RUN_MAX_SMALL (1U << RUN_MAX_SMALL_2POW)
+#define RUN_MAX_SMALL (12 * pagesize)
/*
* Hyper-threaded CPUs may need a special instruction inside spin loops in
@@ -319,6 +386,15 @@
*/
#define BLOCK_COST_2POW 4
+#ifdef MALLOC_MAG
+ /*
+ * Default magazine size, in bytes. max_rounds is calculated to make
+ * optimal use of the space, leaving just enough room for the magazine
+ * header.
+ */
+# define MAG_SIZE_2POW_DEFAULT 9
+#endif
+
#ifdef MALLOC_BALANCE
/*
* We use an exponential moving average to track recent lock contention,
@@ -369,6 +445,11 @@
*/
uint64_t nrequests;
+#ifdef MALLOC_MAG
+ /* Number of magazine reloads from this bin. */
+ uint64_t nmags;
+#endif
+
/* Total number of runs created for this bin's size class. */
uint64_t nruns;
@@ -678,6 +759,35 @@
/******************************************************************************/
/*
+ * Magazine data structures.
+ */
+
+#ifdef MALLOC_MAG
+typedef struct mag_s mag_t;
+struct mag_s {
+ size_t binind; /* Index of associated bin. */
+ size_t nrounds;
+ void *rounds[1]; /* Dynamically sized. */
+};
+
+/*
+ * Magazines are lazily allocated, but once created, they remain until the
+ * associated mag_rack is destroyed.
+ */
+typedef struct bin_mags_s bin_mags_t;
+struct bin_mags_s {
+ mag_t *curmag;
+ mag_t *sparemag;
+};
+
+typedef struct mag_rack_s mag_rack_t;
+struct mag_rack_s {
+ bin_mags_t bin_mags[1]; /* Dynamically sized. */
+};
+#endif
+
+/******************************************************************************/
+/*
* Data.
*/
@@ -690,16 +800,147 @@
static size_t pagesize_2pow;
/* Various bin-related settings. */
-static size_t bin_maxclass; /* Max size class for bins. */
-static unsigned ntbins; /* Number of (2^n)-spaced tiny bins. */
+#ifdef MALLOC_TINY /* Number of (2^n)-spaced tiny bins. */
+# define ntbins ((unsigned)(QUANTUM_2POW - TINY_MIN_2POW))
+#else
+# define ntbins 0
+#endif
static unsigned nqbins; /* Number of quantum-spaced bins. */
-static unsigned nsbins; /* Number of (2^n)-spaced sub-page bins. */
-static size_t small_min;
-static size_t small_max;
+static unsigned ncbins; /* Number of cacheline-spaced bins. */
+static unsigned nsbins; /* Number of subpage-spaced bins. */
+static unsigned nbins;
+#ifdef MALLOC_TINY
+# define tspace_max ((size_t)(QUANTUM >> 1))
+#endif
+#define qspace_min QUANTUM
+static size_t qspace_max;
+static size_t cspace_min;
+static size_t cspace_max;
+static size_t sspace_min;
+static size_t sspace_max;
+#define bin_maxclass sspace_max
+
+static uint8_t const *size2bin;
+/*
+ * const_size2bin is a static constant lookup table that in the common case can
+ * be used as-is for size2bin. For dynamically linked programs, this avoids
+ * a page of memory overhead per process.
+ */
+#define S2B_1(i) i,
+#define S2B_2(i) S2B_1(i) S2B_1(i)
+#define S2B_4(i) S2B_2(i) S2B_2(i)
+#define S2B_8(i) S2B_4(i) S2B_4(i)
+#define S2B_16(i) S2B_8(i) S2B_8(i)
+#define S2B_32(i) S2B_16(i) S2B_16(i)
+#define S2B_64(i) S2B_32(i) S2B_32(i)
+#define S2B_128(i) S2B_64(i) S2B_64(i)
+#define S2B_256(i) S2B_128(i) S2B_128(i)
+static const uint8_t const_size2bin[(1U << PAGESIZE_2POW) - 255] = {
+ S2B_1(0xffU) /* 0 */
+#if (QUANTUM_2POW == 4)
+/* 64-bit system ************************/
+# ifdef MALLOC_TINY
+ S2B_2(0) /* 2 */
+ S2B_2(1) /* 4 */
+ S2B_4(2) /* 8 */
+ S2B_8(3) /* 16 */
+# define S2B_QMIN 3
+# else
+ S2B_16(0) /* 16 */
+# define S2B_QMIN 0
+# endif
+ S2B_16(S2B_QMIN + 1) /* 32 */
+ S2B_16(S2B_QMIN + 2) /* 48 */
+ S2B_16(S2B_QMIN + 3) /* 64 */
+ S2B_16(S2B_QMIN + 4) /* 80 */
+ S2B_16(S2B_QMIN + 5) /* 96 */
+ S2B_16(S2B_QMIN + 6) /* 112 */
+ S2B_16(S2B_QMIN + 7) /* 128 */
+# define S2B_CMIN (S2B_QMIN + 8)
+#else
+/* 32-bit system ************************/
+# ifdef MALLOC_TINY
+ S2B_2(0) /* 2 */
+ S2B_2(1) /* 4 */
+ S2B_4(2) /* 8 */
+# define S2B_QMIN 2
+# else
+ S2B_8(0) /* 8 */
+# define S2B_QMIN 0
+# endif
+ S2B_8(S2B_QMIN + 1) /* 16 */
+ S2B_8(S2B_QMIN + 2) /* 24 */
+ S2B_8(S2B_QMIN + 3) /* 32 */
+ S2B_8(S2B_QMIN + 4) /* 40 */
+ S2B_8(S2B_QMIN + 5) /* 48 */
+ S2B_8(S2B_QMIN + 6) /* 56 */
+ S2B_8(S2B_QMIN + 7) /* 64 */
+ S2B_8(S2B_QMIN + 8) /* 72 */
+ S2B_8(S2B_QMIN + 9) /* 80 */
+ S2B_8(S2B_QMIN + 10) /* 88 */
+ S2B_8(S2B_QMIN + 11) /* 96 */
+ S2B_8(S2B_QMIN + 12) /* 104 */
+ S2B_8(S2B_QMIN + 13) /* 112 */
+ S2B_8(S2B_QMIN + 14) /* 120 */
+ S2B_8(S2B_QMIN + 15) /* 128 */
+# define S2B_CMIN (S2B_QMIN + 16)
+#endif
+/****************************************/
+ S2B_64(S2B_CMIN + 0) /* 192 */
+ S2B_64(S2B_CMIN + 1) /* 256 */
+ S2B_64(S2B_CMIN + 2) /* 320 */
+ S2B_64(S2B_CMIN + 3) /* 384 */
+ S2B_64(S2B_CMIN + 4) /* 448 */
+ S2B_64(S2B_CMIN + 5) /* 512 */
+# define S2B_SMIN (S2B_CMIN + 6)
+ S2B_256(S2B_SMIN + 0) /* 768 */
+ S2B_256(S2B_SMIN + 1) /* 1024 */
+ S2B_256(S2B_SMIN + 2) /* 1280 */
+ S2B_256(S2B_SMIN + 3) /* 1536 */
+ S2B_256(S2B_SMIN + 4) /* 1792 */
+ S2B_256(S2B_SMIN + 5) /* 2048 */
+ S2B_256(S2B_SMIN + 6) /* 2304 */
+ S2B_256(S2B_SMIN + 7) /* 2560 */
+ S2B_256(S2B_SMIN + 8) /* 2816 */
+ S2B_256(S2B_SMIN + 9) /* 3072 */
+ S2B_256(S2B_SMIN + 10) /* 3328 */
+ S2B_256(S2B_SMIN + 11) /* 3584 */
+ S2B_256(S2B_SMIN + 12) /* 3840 */
+#if (PAGESIZE_2POW == 13)
+ S2B_256(S2B_SMIN + 13) /* 4096 */
+ S2B_256(S2B_SMIN + 14) /* 4352 */
+ S2B_256(S2B_SMIN + 15) /* 4608 */
+ S2B_256(S2B_SMIN + 16) /* 4864 */
+ S2B_256(S2B_SMIN + 17) /* 5120 */
+ S2B_256(S2B_SMIN + 18) /* 5376 */
+ S2B_256(S2B_SMIN + 19) /* 5632 */
+ S2B_256(S2B_SMIN + 20) /* 5888 */
+ S2B_256(S2B_SMIN + 21) /* 6144 */
+ S2B_256(S2B_SMIN + 22) /* 6400 */
+ S2B_256(S2B_SMIN + 23) /* 6656 */
+ S2B_256(S2B_SMIN + 24) /* 6912 */
+ S2B_256(S2B_SMIN + 25) /* 7168 */
+ S2B_256(S2B_SMIN + 26) /* 7424 */
+ S2B_256(S2B_SMIN + 27) /* 7680 */
+ S2B_256(S2B_SMIN + 28) /* 7936 */
+#endif
+};
+#undef S2B_1
+#undef S2B_2
+#undef S2B_4
+#undef S2B_8
+#undef S2B_16
+#undef S2B_32
+#undef S2B_64
+#undef S2B_128
+#undef S2B_256
+#undef S2B_QMIN
+#undef S2B_CMIN
+#undef S2B_SMIN
-/* Various quantum-related settings. */
-static size_t quantum;
-static size_t quantum_mask; /* (quantum - 1). */
+#ifdef MALLOC_MAG
+static size_t max_rounds;
+#endif
/* Various chunk-related settings. */
static size_t chunksize;
@@ -796,6 +1037,14 @@
static __thread arena_t *arenas_map;
#endif
+#ifdef MALLOC_MAG
+/*
+ * Map of thread-specific magazine racks, used for thread-specific object
+ * caching.
+ */
+static __thread mag_rack_t *mag_rack;
+#endif
+
#ifdef MALLOC_STATS
/* Chunk statistics. */
static chunk_stats_t stats_chunks;
@@ -818,13 +1067,17 @@
static bool opt_dss = true;
static bool opt_mmap = true;
#endif
+#ifdef MALLOC_MAG
+static bool opt_mag = true;
+static size_t opt_mag_size_2pow = MAG_SIZE_2POW_DEFAULT;
+#endif
static size_t opt_dirty_max = DIRTY_MAX_DEFAULT;
#ifdef MALLOC_BALANCE
static uint64_t opt_balance_threshold = BALANCE_THRESHOLD_DEFAULT;
#endif
static bool opt_print_stats = false;
-static size_t opt_quantum_2pow = QUANTUM_2POW_MIN;
-static size_t opt_small_max_2pow = SMALL_MAX_2POW_DEFAULT;
+static size_t opt_qspace_max_2pow = QSPACE_MAX_2POW_DEFAULT;
+static size_t opt_cspace_max_2pow = CSPACE_MAX_2POW_DEFAULT;
static size_t opt_chunk_2pow = CHUNK_2POW_DEFAULT;
static bool opt_utrace = false;
static bool opt_sysv = false;
@@ -902,15 +1155,21 @@
static void arena_run_trim_tail(arena_t *arena, arena_chunk_t *chunk,
arena_run_t *run, size_t oldsize, size_t newsize, bool dirty);
static arena_run_t *arena_bin_nonfull_run_get(arena_t *arena, arena_bin_t *bin);
-static void *arena_bin_malloc_hard(arena_t *arena, arena_bin_t *bin);
-static size_t arena_bin_run_size_calc(arena_bin_t *bin, size_t min_run_size);
+static void *arena_bin_malloc_hard(arena_t *arena, arena_bin_t *bin);
+static size_t arena_bin_run_size_calc(arena_bin_t *bin, size_t min_run_size);
#ifdef MALLOC_BALANCE
static void arena_lock_balance_hard(arena_t *arena);
#endif
+#ifdef MALLOC_MAG
+static void mag_load(mag_t *mag);
+#endif
static void *arena_malloc_large(arena_t *arena, size_t size, bool zero);
static void *arena_palloc(arena_t *arena, size_t alignment, size_t size,
size_t alloc_size);
static size_t arena_salloc(const void *ptr);
+#ifdef MALLOC_MAG
+static void mag_unload(mag_t *mag);
+#endif
static void arena_dalloc_large(arena_t *arena, arena_chunk_t *chunk,
void *ptr);
static void arena_ralloc_large_shrink(arena_t *arena, arena_chunk_t *chunk,
@@ -921,11 +1180,22 @@
static void *arena_ralloc(void *ptr, size_t size, size_t oldsize);
static bool arena_new(arena_t *arena);
static arena_t *arenas_extend(unsigned ind);
+#ifdef MALLOC_MAG
+static mag_t *mag_create(arena_t *arena, size_t binind);
+static void mag_destroy(mag_t *mag);
+static mag_rack_t *mag_rack_create(arena_t *arena);
+static void mag_rack_destroy(mag_rack_t *rack);
+#endif
static void *huge_malloc(size_t size, bool zero);
static void *huge_palloc(size_t alignment, size_t size);
static void *huge_ralloc(void *ptr, size_t size, size_t oldsize);
static void huge_dalloc(void *ptr);
static void malloc_print_stats(void);
+#ifdef MALLOC_DEBUG
+static void size2bin_validate(void);
+#endif
+static bool size2bin_init(void);
+static bool size2bin_init_hard(void);
static bool malloc_init_hard(void);
/*
@@ -1063,18 +1333,23 @@
#define CHUNK_CEILING(s) \
(((s) + chunksize_mask) & ~chunksize_mask)
+/* Return the smallest quantum multiple that is >= a. */
+#define QUANTUM_CEILING(a) \
+ (((a) + QUANTUM_MASK) & ~QUANTUM_MASK)
+
/* Return the smallest cacheline multiple that is >= s. */
#define CACHELINE_CEILING(s) \
- (((s) + (CACHELINE - 1)) & ~(CACHELINE - 1))
+ (((s) + CACHELINE_MASK) & ~CACHELINE_MASK)
-/* Return the smallest quantum multiple that is >= a. */
-#define QUANTUM_CEILING(a) \
- (((a) + quantum_mask) & ~quantum_mask)
+/* Return the smallest subpage multiple that is >= s. */
+#define SUBPAGE_CEILING(s) \
+ (((s) + SUBPAGE_MASK) & ~SUBPAGE_MASK)
/* Return the smallest pagesize multiple that is >= s. */
#define PAGE_CEILING(s) \
(((s) + pagesize_mask) & ~pagesize_mask)
+#ifdef MALLOC_TINY
/* Compute the smallest power of 2 that is >= x. */
static inline size_t
pow2_ceil(size_t x)
@@ -1092,6 +1367,7 @@
x++;
return (x);
}
+#endif
#ifdef MALLOC_BALANCE
/*
@@ -1382,10 +1658,19 @@
arena->stats.ndalloc_small + arena->stats.ndalloc_large);
malloc_printf("mapped: %12zu\n", arena->stats.mapped);
- malloc_printf("bins: bin size regs pgs requests newruns"
- " reruns maxruns curruns\n");
- for (i = 0, gap_start = UINT_MAX; i < ntbins + nqbins + nsbins; i++) {
- if (arena->bins[i].stats.nrequests == 0) {
+#ifdef MALLOC_MAG
+ if (__isthreaded && opt_mag) {
+ malloc_printf("bins: bin size regs pgs mags "
+ "newruns reruns maxruns curruns\n");
+ } else {
+#endif
+ malloc_printf("bins: bin size regs pgs requests "
+ "newruns reruns maxruns curruns\n");
+#ifdef MALLOC_MAG
+ }
+#endif
+ for (i = 0, gap_start = UINT_MAX; i < nbins; i++) {
+ if (arena->bins[i].stats.nruns == 0) {
if (gap_start == UINT_MAX)
gap_start = i;
} else {
@@ -1404,10 +1689,15 @@
"%13u %1s %4u %4u %3u %9llu %9llu"
" %9llu %7lu %7lu\n",
i,
- i < ntbins ? "T" : i < ntbins + nqbins ? "Q" : "S",
+ i < ntbins ? "T" : i < ntbins + nqbins ? "Q" :
+ i < ntbins + nqbins + ncbins ? "C" : "S",
arena->bins[i].reg_size,
arena->bins[i].nregs,
arena->bins[i].run_size >> pagesize_2pow,
+#ifdef MALLOC_MAG
+ (__isthreaded && opt_mag) ?
+ arena->bins[i].stats.nmags :
+#endif
arena->bins[i].stats.nrequests,
arena->bins[i].stats.nruns,
arena->bins[i].stats.reruns,
@@ -2137,44 +2427,9 @@
static inline void
arena_run_reg_dalloc(arena_run_t *run, arena_bin_t *bin, void *ptr, size_t size)
{
- /*
- * To divide by a number D that is not a power of two we multiply
- * by (2^21 / D) and then right shift by 21 positions.
- *
- * X / D
- *
- * becomes
- *
- * (X * size_invs[(D >> QUANTUM_2POW_MIN) - 3]) >> SIZE_INV_SHIFT
- */
-#define SIZE_INV_SHIFT 21
-#define SIZE_INV(s) (((1U << SIZE_INV_SHIFT) / (s << QUANTUM_2POW_MIN)) + 1)
- static const unsigned size_invs[] = {
- SIZE_INV(3),
- SIZE_INV(4), SIZE_INV(5), SIZE_INV(6), SIZE_INV(7),
- SIZE_INV(8), SIZE_INV(9), SIZE_INV(10), SIZE_INV(11),
- SIZE_INV(12),SIZE_INV(13), SIZE_INV(14), SIZE_INV(15),
- SIZE_INV(16),SIZE_INV(17), SIZE_INV(18), SIZE_INV(19),
- SIZE_INV(20),SIZE_INV(21), SIZE_INV(22), SIZE_INV(23),
- SIZE_INV(24),SIZE_INV(25), SIZE_INV(26), SIZE_INV(27),
- SIZE_INV(28),SIZE_INV(29), SIZE_INV(30), SIZE_INV(31)
-#if (QUANTUM_2POW_MIN < 4)
- ,
- SIZE_INV(32), SIZE_INV(33), SIZE_INV(34), SIZE_INV(35),
- SIZE_INV(36), SIZE_INV(37), SIZE_INV(38), SIZE_INV(39),
- SIZE_INV(40), SIZE_INV(41), SIZE_INV(42), SIZE_INV(43),
- SIZE_INV(44), SIZE_INV(45), SIZE_INV(46), SIZE_INV(47),
- SIZE_INV(48), SIZE_INV(49), SIZE_INV(50), SIZE_INV(51),
- SIZE_INV(52), SIZE_INV(53), SIZE_INV(54), SIZE_INV(55),
- SIZE_INV(56), SIZE_INV(57), SIZE_INV(58), SIZE_INV(59),
- SIZE_INV(60), SIZE_INV(61), SIZE_INV(62), SIZE_INV(63)
-#endif
- };
unsigned diff, regind, elm, bit;
assert(run->magic == ARENA_RUN_MAGIC);
- assert(((sizeof(size_invs)) / sizeof(unsigned)) + 3
- >= (SMALL_MAX_DEFAULT >> QUANTUM_2POW_MIN));
/*
* Avoid doing division with a variable divisor if possible. Using
@@ -2203,26 +2458,89 @@
regind = (diff >> log2_table[size - 1]);
else if (size <= 32768)
regind = diff >> (8 + log2_table[(size >> 8) - 1]);
- else {
- /*
- * The run size is too large for us to use the lookup
- * table. Use real division.
- */
+ else
regind = diff / size;
- }
- } else if (size <= (((sizeof(size_invs) / sizeof(unsigned)) + 2)
- << QUANTUM_2POW_MIN)) {
- regind = size_invs[(size >> QUANTUM_2POW_MIN) - 3] * diff;
- regind >>= SIZE_INV_SHIFT;
- } else {
+ } else if (size < qspace_max) {
/*
- * size_invs isn't large enough to handle this size class, so
- * calculate regind using actual division. This only happens
- * if the user increases small_max via the 'S' runtime
- * configuration option.
+ * To divide by a number D that is not a power of two we
+ * multiply by (2^21 / D) and then right shift by 21 positions.
+ *
+ * X / D
+ *
+ * becomes
+ *
+ * (X * qsize_invs[(D >> QUANTUM_2POW) - 3])
+ * >> SIZE_INV_SHIFT
+ *
+ * We can omit the first three elements, because we never
+ * divide by 0, and QUANTUM and 2*QUANTUM are both powers of
+ * two, which are handled above.
*/
- regind = diff / size;
- };
+#define SIZE_INV_SHIFT 21
+#define QSIZE_INV(s) (((1U << SIZE_INV_SHIFT) / (s << QUANTUM_2POW)) + 1)
+ static const unsigned qsize_invs[] = {
+ QSIZE_INV(3),
+ QSIZE_INV(4), QSIZE_INV(5), QSIZE_INV(6), QSIZE_INV(7)
+#if (QUANTUM_2POW < 4)
+ ,
+ QSIZE_INV(8), QSIZE_INV(9), QSIZE_INV(10), QSIZE_INV(11),
+ QSIZE_INV(12),QSIZE_INV(13), QSIZE_INV(14), QSIZE_INV(15)
+#endif
+ };
+ assert(QUANTUM * (((sizeof(qsize_invs)) / sizeof(unsigned)) + 3)
>>> TRUNCATED FOR MAIL (1000 lines) <<<
More information about the p4-projects
mailing list