📄 dlmalloc.c.svn-base
字号:
//==========================================================================
//
// dlmalloc.c
//
// Port of Doug Lea's malloc implementation
//
//==========================================================================
//----------------------------------------------------------------------------
/*
A version of malloc/free/realloc written by Doug Lea and released to the
public domain. Send questions/comments/complaints/performance data
to dl at cs.oswego.edu
* VERSION 2.6.6 Sun Mar 5 19:10:03 2000 Doug Lea (dl at gee)
Note: There may be an updated version of this malloc obtainable at
ftp://g.oswego.edu/pub/misc/malloc.c
Check before installing!
* Why use this malloc?
This is not the fastest, most space-conserving, most portable, or
most tunable malloc ever written. However it is among the fastest
while also being among the most space-conserving, portable and tunable.
Consistent balance across these factors results in a good general-purpose
allocator. For a high-level description, see
http://g.oswego.edu/dl/html/malloc.html
* Synopsis of public routines
(Much fuller descriptions are contained in the program documentation below.)
[ these have of course been renamed in the eCos port ]a
malloc(size_t n);
Return a pointer to a newly allocated chunk of at least n bytes, or null
if no space is available.
free(Void_t* p);
Release the chunk of memory pointed to by p, or no effect if p is null.
realloc(Void_t* p, size_t n);
Return a pointer to a chunk of size n that contains the same data
as does chunk p up to the minimum of (n, p's size) bytes, or null
if no space is available. The returned pointer may or may not be
the same as p. If p is null, equivalent to malloc. realloc of
zero bytes calls free(p)
* Vital statistics:
Alignment: 8-byte
8 byte alignment is currently hardwired into the design. This
seems to suffice for all current machines and C compilers.
Assumed pointer representation: 4 or 8 bytes
Code for 8-byte pointers is untested by me but has worked
reliably by Wolfram Gloger, who contributed most of the
changes supporting this.
Assumed size_t representation: 4 or 8 bytes
Note that size_t is allowed to be 4 bytes even if pointers are 8.
Minimum overhead per allocated chunk: 4 or 8 bytes
Each malloced chunk has a hidden overhead of 4 bytes holding size
and status information.
Minimum allocated size: 4-byte ptrs: 16 bytes (including 4 overhead)
8-byte ptrs: 24/32 bytes (including, 4/8 overhead)
When a chunk is freed, 12 (for 4byte ptrs) or 20 (for 8 byte
ptrs but 4 byte size) or 24 (for 8/8) additional bytes are
needed; 4 (8) for a trailing size field
and 8 (16) bytes for free list pointers. Thus, the minimum
allocatable size is 16/24/32 bytes.
Even a request for zero bytes (i.e., malloc(0)) returns a
pointer to something of the minimum allocatable size.
Maximum allocated size: 4-byte size_t: 2^31 - 8 bytes
8-byte size_t: 2^63 - 16 bytes
It is assumed that (possibly signed) size_t bit values suffice to
represent chunk sizes. `Possibly signed' is due to the fact
that `size_t' may be defined on a system as either a signed or
an unsigned type. To be conservative, values that would appear
as negative numbers are avoided.
Requests for sizes with a negative sign bit when the request
size is treaded as a long will return null.
Maximum overhead wastage per allocated chunk: normally 15 bytes
Alignnment demands, plus the minimum allocatable size restriction
make the normal worst-case wastage 15 bytes (i.e., up to 15
more bytes will be allocated than were requested in malloc), with
one exception: because requests for zero bytes allocate non-zero space,
the worst case wastage for a request of zero bytes is 24 bytes.
* Limitations
Here are some features that are NOT currently supported
* No user-definable hooks for callbacks and the like.
* No automated mechanism for fully checking that all accesses
to malloced memory stay within their bounds.
* No support for compaction.
* Synopsis of compile-time options:
People have reported using previous versions of this malloc on all
versions of Unix, sometimes by tweaking some of the defines
below. It has been tested most extensively on Solaris and
Linux. It is also reported to work on WIN32 platforms.
People have also reported adapting this malloc for use in
stand-alone embedded systems.
The implementation is in straight, hand-tuned ANSI C. Among other
consequences, it uses a lot of macros. Because of this, to be at
all usable, this code should be compiled using an optimizing compiler
(for example gcc -O2) that can simplify expressions and control
paths.
MEMALLOC_ALLOCATOR_DLMALLOC_DEBUG (default: NOT defined)
Define to enable debugging. Adds fairly extensive assertion-based
checking to help track down memory errors, but noticeably slows down
execution.
MALLOC_LOCK (default: NOT defined)
MALLOC_UNLOCK (default: NOT defined)
Define these to C expressions which are run to lock and unlock
the malloc data structures. Calls may be nested; that is,
MALLOC_LOCK may be called more than once before the corresponding
MALLOC_UNLOCK calls. MALLOC_LOCK must avoid waiting for a lock
that it already holds.
MALLOC_ALIGNMENT (default: NOT defined)
Define this to 16 if you need 16 byte alignment instead of 8 byte alignment
which is the normal default.
SIZE_T_SMALLER_THAN_LONG (default: NOT defined)
Define this when the platform you are compiling has
sizeof(long) > sizeof(size_t).
The option causes some extra code to be generated to handle operations
that use size_t operands and have long results.
INTERNAL_SIZE_T (default: size_t)
Define to a 32-bit type (probably `unsigned int') if you are on a
64-bit machine, yet do not want or need to allow malloc requests of
greater than 2^31 to be handled. This saves space, especially for
very small chunks.
*/
//----------------------------------------------------------------------------
/* Preliminaries */
#include <stddef.h> // for size_t
#include "dlmalloc.h"
extern void* memcpy(void *, const void *, size_t);
extern void* memset(void *, int, size_t);
// type definitions
//
#ifndef uint32
#define uint8 unsigned char
#define uint16 unsigned short
#define uint32 unsigned int
#define int8 char
#define int16 short
#define int32 int
#endif // uint32
/*
Debugging:
Because freed chunks may be overwritten with link fields, this
malloc will often die when freed memory is overwritten by user
programs. This can be very effective (albeit in an annoying way)
in helping track down dangling pointers.
If you compile with MEMALLOC_ALLOCATOR_DLMALLOC_DEBUG enabled, a
number of assertion checks are
enabled that will catch more memory errors. You probably won't be
able to make much sense of the actual assertion errors, but they
should help you locate incorrectly overwritten memory. The
checking is fairly extensive, and will slow down execution
noticeably. Calling get_status() with DEBUG set will
attempt to check every allocated and free chunk in the
course of computing the summmaries.
Setting MEMALLOC_ALLOCATOR_DLMALLOC_DEBUG may also be helpful if you
are trying to modify this code. The assertions in the check routines
spell out in more detail the assumptions and invariants underlying
the algorithms.
*/
#ifndef ASSERT
#ifdef _DEBUG_
#include <assert.h>
#define ASSERT(x) assert((x))
#else
#define ASSERT(x)
#endif // _DEBUG_
#endif // ASSERT
/*
Define MALLOC_LOCK and MALLOC_UNLOCK to C expressions to run to
lock and unlock the malloc data structures. MALLOC_LOCK may be
called recursively.
*/
#if 0
#include <asm/system.h> // for save_and_cli() and restore_flags()
static int s_lock_flags;
inline void _MLOCK(void)
{
save_and_cli(s_lock_flags);
}
inline void _MUNLOCK(void)
{
restore_flags(s_lock_flags);
}
#define MALLOC_LOCK _MLOCK()
#define MALLOC_UNLOCK _MUNLOCK()
#endif
#ifndef MALLOC_LOCK
#define MALLOC_LOCK
#endif
#ifndef MALLOC_UNLOCK
#define MALLOC_UNLOCK
#endif
/*
INTERNAL_SIZE_T is the word-size used for internal bookkeeping
of chunk sizes. On a 64-bit machine, you can reduce malloc
overhead by defining INTERNAL_SIZE_T to be a 32 bit `unsigned int'
at the expense of not being able to handle requests greater than
2^31. This limitation is hardly ever a concern; you are encouraged
to set this. However, the default version is the same as size_t.
*/
#ifndef INTERNAL_SIZE_T
#define INTERNAL_SIZE_T size_t
#endif
/*
Following is needed on implementations whereby long > size_t.
The problem is caused because the code performs subtractions of
size_t values and stores the result in long values. In the case
where long > size_t and the first value is actually less than
the second value, the resultant value is positive. For example,
(long)(x - y) where x = 0 and y is 1 ends up being 0x00000000FFFFFFFF
which is 2*31 - 1 instead of 0xFFFFFFFFFFFFFFFF. This is due to the
fact that assignment from unsigned to signed won't sign extend.
*/
#ifdef SIZE_T_SMALLER_THAN_LONG
#define long_sub_size_t(x, y) ( (x < y) ? -((long)(y - x)) : (x - y) );
#else
#define long_sub_size_t(x, y) ( (long)(x - y) )
#endif
/*
#define MEMALLOC_ALLOCATOR_DLMALLOC_USE_MEMCPY
*/
#ifdef MEMALLOC_ALLOCATOR_DLMALLOC_USE_MEMCPY
#include <string.h> // memcpy, memset
/* The following macros are only invoked with (2n+1)-multiples of
INTERNAL_SIZE_T units, with a positive integer n. This is exploited
for fast inline execution when n is small. */
#define MALLOC_ZERO(charp, nbytes) \
do { \
INTERNAL_SIZE_T mzsz = (nbytes); \
if(mzsz <= 9*sizeof(mzsz)) { \
INTERNAL_SIZE_T* mz = (INTERNAL_SIZE_T*) (charp); \
if(mzsz >= 5*sizeof(mzsz)) { *mz++ = 0; \
*mz++ = 0; \
if(mzsz >= 7*sizeof(mzsz)) { *mz++ = 0; \
*mz++ = 0; \
if(mzsz >= 9*sizeof(mzsz)) { *mz++ = 0; \
*mz++ = 0; }}} \
*mz++ = 0; \
*mz++ = 0; \
*mz = 0; \
} else memset((charp), 0, mzsz); \
} while(0)
#define MALLOC_COPY(dest,src,nbytes) \
do { \
INTERNAL_SIZE_T mcsz = (nbytes); \
if(mcsz <= 9*sizeof(mcsz)) { \
INTERNAL_SIZE_T* mcsrc = (INTERNAL_SIZE_T*) (src); \
INTERNAL_SIZE_T* mcdst = (INTERNAL_SIZE_T*) (dest); \
if(mcsz >= 5*sizeof(mcsz)) { *mcdst++ = *mcsrc++; \
*mcdst++ = *mcsrc++; \
if(mcsz >= 7*sizeof(mcsz)) { *mcdst++ = *mcsrc++; \
*mcdst++ = *mcsrc++; \
if(mcsz >= 9*sizeof(mcsz)) { *mcdst++ = *mcsrc++; \
*mcdst++ = *mcsrc++; }}} \
*mcdst++ = *mcsrc++; \
*mcdst++ = *mcsrc++; \
*mcdst = *mcsrc ; \
} else memcpy(dest, src, mcsz); \
} while(0)
#else /* !MEMALLOC_ALLOCATOR_DLMALLOC_USE_MEMCPY */
/* Use Duff's device for good zeroing/copying performance. */
#define MALLOC_ZERO(charp, nbytes) \
do { \
INTERNAL_SIZE_T* mzp = (INTERNAL_SIZE_T*)(charp); \
long mctmp = (nbytes)/sizeof(INTERNAL_SIZE_T), mcn; \
if (mctmp < 8) mcn = 0; else { mcn = (mctmp-1)/8; mctmp %= 8; } \
switch (mctmp) { \
case 0: for(;;) { *mzp++ = 0; \
case 7: *mzp++ = 0; \
case 6: *mzp++ = 0; \
case 5: *mzp++ = 0; \
case 4: *mzp++ = 0; \
case 3: *mzp++ = 0; \
case 2: *mzp++ = 0; \
case 1: *mzp++ = 0; if(mcn <= 0) break; mcn--; } \
} \
} while(0)
#define MALLOC_COPY(dest,src,nbytes) \
do { \
INTERNAL_SIZE_T* mcsrc = (INTERNAL_SIZE_T*) src; \
INTERNAL_SIZE_T* mcdst = (INTERNAL_SIZE_T*) dest; \
long mctmp = (nbytes)/sizeof(INTERNAL_SIZE_T), mcn; \
if (mctmp < 8) mcn = 0; else { mcn = (mctmp-1)/8; mctmp %= 8; } \
switch (mctmp) { \
case 0: for(;;) { *mcdst++ = *mcsrc++; \
case 7: *mcdst++ = *mcsrc++; \
case 6: *mcdst++ = *mcsrc++; \
case 5: *mcdst++ = *mcsrc++; \
case 4: *mcdst++ = *mcsrc++; \
case 3: *mcdst++ = *mcsrc++; \
case 2: *mcdst++ = *mcsrc++; \
case 1: *mcdst++ = *mcsrc++; if(mcn <= 0) break; mcn--; } \
} \
} while(0)
#endif // MEMALLOC_ALLOCATOR_DLMALLOC_USE_MEMCPY
//----------------------------------------------------------------------------
/*
malloc_chunk details:
(The following includes lightly edited explanations by Colin Plumb.)
Chunks of memory are maintained using a `boundary tag' method as
described in e.g., Knuth or Standish. (See the paper by Paul
Wilson ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a
survey of such techniques.) Sizes of free chunks are stored both
in the front of each chunk and at the end. This makes
consolidating fragmented chunks into bigger chunks very fast. The
size fields also hold bits representing whether chunks are free or
in use.
An allocated chunk looks like this:
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of previous chunk, if allocated | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of chunk, in bytes |P|
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| User data starts here... .
. .
. (malloc_usable_space() bytes) .
. |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of chunk |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Where "chunk" is the front of the chunk for the purpose of most of
the malloc code, but "mem" is the pointer that is returned to the
user. "Nextchunk" is the beginning of the next contiguous chunk.
Chunks always begin on even word boundries, so the mem portion
(which is returned to the user) is also on an even word boundary, and
thus double-word aligned.
Free chunks are stored in circular doubly-linked lists, and look like this:
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of previous chunk |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
`head:' | Size of chunk, in bytes |P|
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Forward pointer to next chunk in list |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Back pointer to previous chunk in list |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Unused space (may be 0 bytes long) .
. .
. |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
`foot:' | Size of chunk, in bytes |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The P (PREV_INUSE) bit, stored in the unused low-order bit of the
chunk size (which is always a multiple of two words), is an in-use
bit for the *previous* chunk. If that bit is *clear*, then the
word before the current chunk size contains the previous chunk
size, and can be used to find the front of the previous chunk.
(The very first chunk allocated always has this bit set,
preventing access to non-existent (or non-owned) memory.)
Note that the `foot' of the current chunk is actually represented
as the prev_size of the NEXT chunk. (This makes it easier to
deal with alignments etc).
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -