[Spice-devel] [PATCH qxl-wddm-dod v2 12/25] Rename mspace.c to mspace.cpp
Frediano Ziglio
fziglio at redhat.com
Mon Sep 5 18:26:29 UTC 2016
Why the rationale was removed?
By the way this was a workaround for a VS bug, get Visual Studio 2015 Update 1 (actually we are at update 3)
Nack
Frediano
>
> Signed-off-by: Sameeh Jubran <sameeh at daynix.com>
> ---
> qxldod/mspace.c | 2437
> -----------------------------------------
> qxldod/mspace.cpp | 2437
> +++++++++++++++++++++++++++++++++++++++++
> qxldod/qxldod.vcxproj | 2 +-
> qxldod/qxldod.vcxproj.filters | 2 +-
> 4 files changed, 2439 insertions(+), 2439 deletions(-)
> delete mode 100755 qxldod/mspace.c
> create mode 100755 qxldod/mspace.cpp
>
> diff --git a/qxldod/mspace.c b/qxldod/mspace.c
> deleted file mode 100755
> index d0ba123..0000000
> --- a/qxldod/mspace.c
> +++ /dev/null
> @@ -1,2437 +0,0 @@
> -// based on dlmalloc from Doug Lea
> -
> -
> -// quote from the Doug Lea original file
> - /*
> - This is a version (aka dlmalloc) of malloc/free/realloc written by
> - Doug Lea and released to the public domain, as explained at
> - http://creativecommons.org/licenses/publicdomain. Send questions,
> - comments, complaints, performance data, etc to dl at cs.oswego.edu
> -
> - * Version 2.8.3 Thu Sep 22 11:16:15 2005 Doug Lea (dl at gee)
> -
> - Note: There may be an updated version of this malloc obtainable at
> - ftp://gee.cs.oswego.edu/pub/misc/malloc.c
> - Check before installing!
> - */
> -
> -
> -#include <ntddk.h>
> -
> -#include "mspace.h"
> -
> -#pragma warning( disable : 4146 ) /* no "unsigned" warnings */
> -
> -#define MALLOC_ALIGNMENT ((size_t)8U)
> -#define USE_LOCKS 0
> -#define malloc_getpagesize ((size_t)4096U)
> -#define DEFAULT_GRANULARITY malloc_getpagesize
> -#define MAX_SIZE_T (~(size_t)0)
> -#define MALLOC_FAILURE_ACTION
> -#define MALLINFO_FIELD_TYPE size_t
> -#define FOOTERS 0
> -#define INSECURE 0
> -#define PROCEED_ON_ERROR 0
> -#define DEBUG 0
> -#define ABORT_ON_ASSERT_FAILURE 1
> -#define ABORT(user_data) abort_func(user_data)
> -#define USE_BUILTIN_FFS 0
> -#define USE_DEV_RANDOM 0
> -#define PRINT(params) print_func params
> -
> -
> -#define MEMCPY(dest, src, n) RtlCopyMemory(dest, src, n)
> -#define MEMCLEAR(dest, n) RtlZeroMemory(dest, n)
> -
> -
> -#define M_GRANULARITY (-1)
> -
> -void default_abort_func(void *user_data)
> -{
> - for (;;);
> -}
> -
> -void default_print_func(void *user_data, char *format, ...)
> -{
> -}
> -
> -static mspace_abort_t abort_func = default_abort_func;
> -static mspace_print_t print_func = default_print_func;
> -
> -void mspace_set_abort_func(mspace_abort_t f)
> -{
> - abort_func = f;
> -}
> -
> -void mspace_set_print_func(mspace_print_t f)
> -{
> - print_func = f;
> -}
> -
> -/* ------------------------ Mallinfo declarations ------------------------
> */
> -
> -#if !NO_MALLINFO
> -/*
> - This version of malloc supports the standard SVID/XPG mallinfo
> - routine that returns a struct containing usage properties and
> - statistics. It should work on any system that has a
> - /usr/include/malloc.h defining struct mallinfo. The main
> - declaration needed is the mallinfo struct that is returned (by-copy)
> - by mallinfo(). The malloinfo struct contains a bunch of fields that
> - are not even meaningful in this version of malloc. These fields are
> - are instead filled by mallinfo() with other numbers that might be of
> - interest.
> -
> - HAVE_USR_INCLUDE_MALLOC_H should be set if you have a
> - /usr/include/malloc.h file that includes a declaration of struct
> - mallinfo. If so, it is included; else a compliant version is
> - declared below. These must be precisely the same for mallinfo() to
> - work. The original SVID version of this struct, defined on most
> - systems with mallinfo, declares all fields as ints. But some others
> - define as unsigned long. If your system defines the fields using a
> - type of different width than listed here, you MUST #include your
> - system version and #define HAVE_USR_INCLUDE_MALLOC_H.
> -*/
> -
> -/* #define HAVE_USR_INCLUDE_MALLOC_H */
> -
> -
> -struct mallinfo {
> - MALLINFO_FIELD_TYPE arena; /* non-mmapped space allocated from system
> */
> - MALLINFO_FIELD_TYPE ordblks; /* number of free chunks */
> - MALLINFO_FIELD_TYPE smblks; /* always 0 */
> - MALLINFO_FIELD_TYPE hblks; /* always 0 */
> - MALLINFO_FIELD_TYPE hblkhd; /* space in mmapped regions */
> - MALLINFO_FIELD_TYPE usmblks; /* maximum total allocated space */
> - MALLINFO_FIELD_TYPE fsmblks; /* always 0 */
> - MALLINFO_FIELD_TYPE uordblks; /* total allocated space */
> - MALLINFO_FIELD_TYPE fordblks; /* total free space */
> - MALLINFO_FIELD_TYPE keepcost; /* releasable (via malloc_trim) space */
> -};
> -
> -#endif /* NO_MALLINFO */
> -
> -
> -
> -#ifdef DEBUG
> -#if ABORT_ON_ASSERT_FAILURE
> -#define assert(user_data, x) if(!(x)) ABORT(user_data)
> -#else /* ABORT_ON_ASSERT_FAILURE */
> -#include <assert.h>
> -#endif /* ABORT_ON_ASSERT_FAILURE */
> -#else /* DEBUG */
> -#define assert(user_data, x)
> -#endif /* DEBUG */
> -
> -/* ------------------- size_t and alignment properties --------------------
> */
> -
> -/* The byte and bit size of a size_t */
> -#define SIZE_T_SIZE (sizeof(size_t))
> -#define SIZE_T_BITSIZE (sizeof(size_t) << 3)
> -
> -/* Some constants coerced to size_t */
> -/* Annoying but necessary to avoid errors on some plaftorms */
> -#define SIZE_T_ZERO ((size_t)0)
> -#define SIZE_T_ONE ((size_t)1)
> -#define SIZE_T_TWO ((size_t)2)
> -#define TWO_SIZE_T_SIZES (SIZE_T_SIZE<<1)
> -#define FOUR_SIZE_T_SIZES (SIZE_T_SIZE<<2)
> -#define SIX_SIZE_T_SIZES (FOUR_SIZE_T_SIZES+TWO_SIZE_T_SIZES)
> -#define HALF_MAX_SIZE_T (MAX_SIZE_T / 2U)
> -
> -/* The bit mask value corresponding to MALLOC_ALIGNMENT */
> -#define CHUNK_ALIGN_MASK (MALLOC_ALIGNMENT - SIZE_T_ONE)
> -
> -/* True if address a has acceptable alignment */
> -#define is_aligned(A) (((size_t)((A)) & (CHUNK_ALIGN_MASK)) == 0)
> -
> -/* the number of bytes to offset an address to align it */
> -#define align_offset(A)\
> - ((((size_t)(A) & CHUNK_ALIGN_MASK) == 0)? 0 :\
> - ((MALLOC_ALIGNMENT - ((size_t)(A) & CHUNK_ALIGN_MASK)) &
> CHUNK_ALIGN_MASK))
> -
> -/* --------------------------- Lock preliminaries ------------------------
> */
> -
> -#if USE_LOCKS
> -
> -/*
> - When locks are defined, there are up to two global locks:
> -
> - * If HAVE_MORECORE, morecore_mutex protects sequences of calls to
> - MORECORE. In many cases sys_alloc requires two calls, that should
> - not be interleaved with calls by other threads. This does not
> - protect against direct calls to MORECORE by other threads not
> - using this lock, so there is still code to cope the best we can on
> - interference.
> -
> - * magic_init_mutex ensures that mparams.magic and other
> - unique mparams values are initialized only once.
> -*/
> -
> -
> -#define USE_LOCK_BIT (2U)
> -#else /* USE_LOCKS */
> -#define USE_LOCK_BIT (0U)
> -#define INITIAL_LOCK(l)
> -#endif /* USE_LOCKS */
> -
> -#if USE_LOCKS
> -#define ACQUIRE_MAGIC_INIT_LOCK() ACQUIRE_LOCK(&magic_init_mutex);
> -#define RELEASE_MAGIC_INIT_LOCK() RELEASE_LOCK(&magic_init_mutex);
> -#else /* USE_LOCKS */
> -#define ACQUIRE_MAGIC_INIT_LOCK()
> -#define RELEASE_MAGIC_INIT_LOCK()
> -#endif /* USE_LOCKS */
> -
> -
> -
> -/* ----------------------- Chunk representations ------------------------
> */
> -
> -/*
> - (The following includes lightly edited explanations by Colin Plumb.)
> -
> - The malloc_chunk declaration below is misleading (but accurate and
> - necessary). It declares a "view" into memory allowing access to
> - necessary fields at known offsets from a given base.
> -
> - Chunks of memory are maintained using a `boundary tag' method as
> - originally described by Knuth. (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 fast. The head fields also hold bits
> - representing whether chunks are free or in use.
> -
> - Here are some pictures to make it clearer. They are "exploded" to
> - show that the state of a chunk can be thought of as extending from
> - the high 31 bits of the head field of its header through the
> - prev_foot and PINUSE_BIT bit of the following chunk header.
> -
> - A chunk that's in use looks like:
> -
> - chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> - | Size of previous chunk (if P = 1) |
> - +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> - +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|
> - | Size of this chunk 1| +-+
> - mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> - | |
> - +- -+
> - | |
> - +- -+
> - | :
> - +- size - sizeof(size_t) available payload bytes -+
> - : |
> - chunk-> +- -+
> - | |
> - +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> - +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1|
> - | Size of next chunk (may or may not be in use) | +-+
> - mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> -
> - And if it's free, it looks like this:
> -
> - chunk-> +- -+
> - | User payload (must be in use, or we would have merged!) |
> - +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> - +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|
> - | Size of this chunk 0| +-+
> - mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> - | Next pointer |
> - +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> - | Prev pointer |
> - +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> - | :
> - +- size - sizeof(struct chunk) unused bytes -+
> - : |
> - chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> - | Size of this chunk |
> - +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> - +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0|
> - | Size of next chunk (must be in use, or we would have merged)| +-+
> - mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> - | :
> - +- User payload -+
> - : |
> - +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> - |0|
> - +-+
> - Note that since we always merge adjacent free chunks, the chunks
> - adjacent to a free chunk must be in use.
> -
> - Given a pointer to a chunk (which can be derived trivially from the
> - payload pointer) we can, in O(1) time, find out whether the adjacent
> - chunks are free, and if so, unlink them from the lists that they
> - are on and merge them with the current chunk.
> -
> - Chunks always begin on even word boundaries, so the mem portion
> - (which is returned to the user) is also on an even word boundary, and
> - thus at least double-word aligned.
> -
> - The P (PINUSE_BIT) 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. If pinuse is set for
> - any given chunk, then you CANNOT determine the size of the
> - previous chunk, and might even get a memory addressing fault when
> - trying to do so.
> -
> - The C (CINUSE_BIT) bit, stored in the unused second-lowest bit of
> - the chunk size redundantly records whether the current chunk is
> - inuse. This redundancy enables usage checks within free and realloc,
> - and reduces indirection when freeing and consolidating chunks.
> -
> - Each freshly allocated chunk must have both cinuse and pinuse set.
> - That is, each allocated chunk borders either a previously allocated
> - and still in-use chunk, or the base of its memory arena. This is
> - ensured by making all allocations from the the `lowest' part of any
> - found chunk. Further, no free chunk physically borders another one,
> - so each free chunk is known to be preceded and followed by either
> - inuse chunks or the ends of memory.
> -
> - Note that the `foot' of the current chunk is actually represented
> - as the prev_foot of the NEXT chunk. This makes it easier to
> - deal with alignments etc but can be very confusing when trying
> - to extend or adapt this code.
> -
> - The exceptions to all this are
> -
> - 1. The special chunk `top' is the top-most available chunk (i.e.,
> - the one bordering the end of available memory). It is treated
> - specially. Top is never included in any bin, is used only if
> - no other chunk is available, and is released back to the
> - system if it is very large (see M_TRIM_THRESHOLD). In effect,
> - the top chunk is treated as larger (and thus less well
> - fitting) than any other available chunk. The top chunk
> - doesn't update its trailing size field since there is no next
> - contiguous chunk that would have to index off it. However,
> - space is still allocated for it (TOP_FOOT_SIZE) to enable
> - separation or merging when space is extended.
> -
> - 3. Chunks allocated via mmap, which have the lowest-order bit
> - (IS_MMAPPED_BIT) set in their prev_foot fields, and do not set
> - PINUSE_BIT in their head fields. Because they are allocated
> - one-by-one, each must carry its own prev_foot field, which is
> - also used to hold the offset this chunk has within its mmapped
> - region, which is needed to preserve alignment. Each mmapped
> - chunk is trailed by the first two fields of a fake next-chunk
> - for sake of usage checks.
> -
> -*/
> -
> -struct malloc_chunk {
> - size_t prev_foot; /* Size of previous chunk (if free). */
> - size_t head; /* Size and inuse bits. */
> - struct malloc_chunk* fd; /* double links -- used only if free. */
> - struct malloc_chunk* bk;
> -};
> -
> -typedef struct malloc_chunk mchunk;
> -typedef struct malloc_chunk* mchunkptr;
> -typedef struct malloc_chunk* sbinptr; /* The type of bins of chunks */
> -typedef unsigned int bindex_t; /* Described below */
> -typedef unsigned int binmap_t; /* Described below */
> -typedef unsigned int flag_t; /* The type of various bit flag sets
> */
> -
> -
> -/* ------------------- Chunks sizes and alignments -----------------------
> */
> -
> -#define MCHUNK_SIZE (sizeof(mchunk))
> -
> -#if FOOTERS
> -#define CHUNK_OVERHEAD (TWO_SIZE_T_SIZES)
> -#else /* FOOTERS */
> -#define CHUNK_OVERHEAD (SIZE_T_SIZE)
> -#endif /* FOOTERS */
> -
> -/* The smallest size we can malloc is an aligned minimal chunk */
> -#define MIN_CHUNK_SIZE\
> - ((MCHUNK_SIZE + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)
> -
> -/* conversion from malloc headers to user pointers, and back */
> -#define chunk2mem(p) ((void*)((char*)(p) + TWO_SIZE_T_SIZES))
> -#define mem2chunk(mem) ((mchunkptr)((char*)(mem) - TWO_SIZE_T_SIZES))
> -/* chunk associated with aligned address A */
> -#define align_as_chunk(A) (mchunkptr)((A) + align_offset(chunk2mem(A)))
> -
> -/* Bounds on request (not chunk) sizes. */
> -#define MAX_REQUEST ((-MIN_CHUNK_SIZE) << 2)
> -#define MIN_REQUEST (MIN_CHUNK_SIZE - CHUNK_OVERHEAD - SIZE_T_ONE)
> -
> -/* pad request bytes into a usable size */
> -#define pad_request(req) \
> - (((req) + CHUNK_OVERHEAD + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)
> -
> -/* pad request, checking for minimum (but not maximum) */
> -#define request2size(req) \
> - (((req) < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(req))
> -
> -/* ------------------ Operations on head and foot fields -----------------
> */
> -
> -/*
> - The head field of a chunk is or'ed with PINUSE_BIT when previous
> - adjacent chunk in use, and or'ed with CINUSE_BIT if this chunk is in
> - use. If the chunk was obtained with mmap, the prev_foot field has
> - IS_MMAPPED_BIT set, otherwise holding the offset of the base of the
> - mmapped region to the base of the chunk.
> -*/
> -
> -#define PINUSE_BIT (SIZE_T_ONE)
> -#define CINUSE_BIT (SIZE_T_TWO)
> -#define INUSE_BITS (PINUSE_BIT|CINUSE_BIT)
> -
> -/* Head value for fenceposts */
> -#define FENCEPOST_HEAD (INUSE_BITS|SIZE_T_SIZE)
> -
> -/* extraction of fields from head words */
> -#define cinuse(p) ((p)->head & CINUSE_BIT)
> -#define pinuse(p) ((p)->head & PINUSE_BIT)
> -#define chunksize(p) ((p)->head & ~(INUSE_BITS))
> -
> -#define clear_pinuse(p) ((p)->head &= ~PINUSE_BIT)
> -#define clear_cinuse(p) ((p)->head &= ~CINUSE_BIT)
> -
> -/* Treat space at ptr +/- offset as a chunk */
> -#define chunk_plus_offset(p, s) ((mchunkptr)(((char*)(p)) + (s)))
> -#define chunk_minus_offset(p, s) ((mchunkptr)(((char*)(p)) - (s)))
> -
> -/* Ptr to next or previous physical malloc_chunk. */
> -#define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->head &
> ~INUSE_BITS)))
> -#define prev_chunk(p) ((mchunkptr)( ((char*)(p)) - ((p)->prev_foot) ))
> -
> -/* extract next chunk's pinuse bit */
> -#define next_pinuse(p) ((next_chunk(p)->head) & PINUSE_BIT)
> -
> -/* Get/set size at footer */
> -#define get_foot(p, s) (((mchunkptr)((char*)(p) + (s)))->prev_foot)
> -#define set_foot(p, s) (((mchunkptr)((char*)(p) + (s)))->prev_foot = (s))
> -
> -/* Set size, pinuse bit, and foot */
> -#define set_size_and_pinuse_of_free_chunk(p, s)\
> - ((p)->head = (s|PINUSE_BIT), set_foot(p, s))
> -
> -/* Set size, pinuse bit, foot, and clear next pinuse */
> -#define set_free_with_pinuse(p, s, n)\
> - (clear_pinuse(n), set_size_and_pinuse_of_free_chunk(p, s))
> -
> -/* Get the internal overhead associated with chunk p */
> -#define overhead_for(p) CHUNK_OVERHEAD
> -
> -/* Return true if malloced space is not necessarily cleared */
> -#define calloc_must_clear(p) (1)
> -
> -
> -/* ---------------------- Overlaid data structures -----------------------
> */
> -
> -/*
> - When chunks are not in use, they are treated as nodes of either
> - lists or trees.
> -
> - "Small" 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
> |
> -
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> -
> - Larger chunks are kept in a form of bitwise digital trees (aka
> - tries) keyed on chunksizes. Because malloc_tree_chunks are only for
> - free chunks greater than 256 bytes, their size doesn't impose any
> - constraints on user chunk sizes. Each node looks like:
> -
> - chunk->
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> - | Size of previous chunk
> |
> -
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> - `head:' | Size of chunk, in bytes
> |P|
> - mem->
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> - | Forward pointer to next chunk of same size
> |
> -
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> - | Back pointer to previous chunk of same size
> |
> -
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> - | Pointer to left child (child[0])
> |
> -
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> - | Pointer to right child (child[1])
> |
> -
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> - | Pointer to parent
> |
> -
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> - | bin index of this chunk
> |
> -
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> - | Unused space
> .
> - .
> |
> -nextchunk->
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> - `foot:' | Size of chunk, in bytes
> |
> -
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> -
> - Each tree holding treenodes is a tree of unique chunk sizes. Chunks
> - of the same size are arranged in a circularly-linked list, with only
> - the oldest chunk (the next to be used, in our FIFO ordering)
> - actually in the tree. (Tree members are distinguished by a non-null
> - parent pointer.) If a chunk with the same size an an existing node
> - is inserted, it is linked off the existing node using pointers that
> - work in the same way as fd/bk pointers of small chunks.
> -
> - Each tree contains a power of 2 sized range of chunk sizes (the
> - smallest is 0x100 <= x < 0x180), which is is divided in half at each
> - tree level, with the chunks in the smaller half of the range (0x100
> - <= x < 0x140 for the top nose) in the left subtree and the larger
> - half (0x140 <= x < 0x180) in the right subtree. This is, of course,
> - done by inspecting individual bits.
> -
> - Using these rules, each node's left subtree contains all smaller
> - sizes than its right subtree. However, the node at the root of each
> - subtree has no particular ordering relationship to either. (The
> - dividing line between the subtree sizes is based on trie relation.)
> - If we remove the last chunk of a given size from the interior of the
> - tree, we need to replace it with a leaf node. The tree ordering
> - rules permit a node to be replaced by any leaf below it.
> -
> - The smallest chunk in a tree (a common operation in a best-fit
> - allocator) can be found by walking a path to the leftmost leaf in
> - the tree. Unlike a usual binary tree, where we follow left child
> - pointers until we reach a null, here we follow the right child
> - pointer any time the left one is null, until we reach a leaf with
> - both child pointers null. The smallest chunk in the tree will be
> - somewhere along that path.
> -
> - The worst case number of steps to add, find, or remove a node is
> - bounded by the number of bits differentiating chunks within
> - bins. Under current bin calculations, this ranges from 6 up to 21
> - (for 32 bit sizes) or up to 53 (for 64 bit sizes). The typical case
> - is of course much better.
> -*/
> -
> -struct malloc_tree_chunk {
> - /* The first four fields must be compatible with malloc_chunk */
> - size_t prev_foot;
> - size_t head;
> - struct malloc_tree_chunk* fd;
> - struct malloc_tree_chunk* bk;
> -
> - struct malloc_tree_chunk* child[2];
> - struct malloc_tree_chunk* parent;
> - bindex_t index;
> -};
> -
> -typedef struct malloc_tree_chunk tchunk;
> -typedef struct malloc_tree_chunk* tchunkptr;
> -typedef struct malloc_tree_chunk* tbinptr; /* The type of bins of trees */
> -
> -/* A little helper macro for trees */
> -#define leftmost_child(t) ((t)->child[0] != 0? (t)->child[0] :
> (t)->child[1])
> -
> -/* ----------------------------- Segments --------------------------------
> */
> -
> -/*
> - Each malloc space may include non-contiguous segments, held in a
> - list headed by an embedded malloc_segment record representing the
> - top-most space. Segments also include flags holding properties of
> - the space. Large chunks that are directly allocated by mmap are not
> - included in this list. They are instead independently created and
> - destroyed without otherwise keeping track of them.
> -
> - Segment management mainly comes into play for spaces allocated by
> - MMAP. Any call to MMAP might or might not return memory that is
> - adjacent to an existing segment. MORECORE normally contiguously
> - extends the current space, so this space is almost always adjacent,
> - which is simpler and faster to deal with. (This is why MORECORE is
> - used preferentially to MMAP when both are available -- see
> - sys_alloc.) When allocating using MMAP, we don't use any of the
> - hinting mechanisms (inconsistently) supported in various
> - implementations of unix mmap, or distinguish reserving from
> - committing memory. Instead, we just ask for space, and exploit
> - contiguity when we get it. It is probably possible to do
> - better than this on some systems, but no general scheme seems
> - to be significantly better.
> -
> - Management entails a simpler variant of the consolidation scheme
> - used for chunks to reduce fragmentation -- new adjacent memory is
> - normally prepended or appended to an existing segment. However,
> - there are limitations compared to chunk consolidation that mostly
> - reflect the fact that segment processing is relatively infrequent
> - (occurring only when getting memory from system) and that we
> - don't expect to have huge numbers of segments:
> -
> - * Segments are not indexed, so traversal requires linear scans. (It
> - would be possible to index these, but is not worth the extra
> - overhead and complexity for most programs on most platforms.)
> - * New segments are only appended to old ones when holding top-most
> - memory; if they cannot be prepended to others, they are held in
> - different segments.
> -
> - Except for the top-most segment of an mstate, each segment record
> - is kept at the tail of its segment. Segments are added by pushing
> - segment records onto the list headed by &mstate.seg for the
> - containing mstate.
> -
> - Segment flags control allocation/merge/deallocation policies:
> - * If EXTERN_BIT set, then we did not allocate this segment,
> - and so should not try to deallocate or merge with others.
> - (This currently holds only for the initial segment passed
> - into create_mspace_with_base.)
> - * If IS_MMAPPED_BIT set, the segment may be merged with
> - other surrounding mmapped segments and trimmed/de-allocated
> - using munmap.
> - * If neither bit is set, then the segment was obtained using
> - MORECORE so can be merged with surrounding MORECORE'd segments
> - and deallocated/trimmed using MORECORE with negative arguments.
> -*/
> -
> -struct malloc_segment {
> - char* base; /* base address */
> - size_t size; /* allocated size */
> - struct malloc_segment* next; /* ptr to next segment */
> -};
> -
> -typedef struct malloc_segment msegment;
> -typedef struct malloc_segment* msegmentptr;
> -
> -/* ---------------------------- malloc_state -----------------------------
> */
> -
> -/*
> - A malloc_state holds all of the bookkeeping for a space.
> - The main fields are:
> -
> - Top
> - The topmost chunk of the currently active segment. Its size is
> - cached in topsize. The actual size of topmost space is
> - topsize+TOP_FOOT_SIZE, which includes space reserved for adding
> - fenceposts and segment records if necessary when getting more
> - space from the system. The size at which to autotrim top is
> - cached from mparams in trim_check, except that it is disabled if
> - an autotrim fails.
> -
> - Designated victim (dv)
> - This is the preferred chunk for servicing small requests that
> - don't have exact fits. It is normally the chunk split off most
> - recently to service another small request. Its size is cached in
> - dvsize. The link fields of this chunk are not maintained since it
> - is not kept in a bin.
> -
> - SmallBins
> - An array of bin headers for free chunks. These bins hold chunks
> - with sizes less than MIN_LARGE_SIZE bytes. Each bin contains
> - chunks of all the same size, spaced 8 bytes apart. To simplify
> - use in double-linked lists, each bin header acts as a malloc_chunk
> - pointing to the real first node, if it exists (else pointing to
> - itself). This avoids special-casing for headers. But to avoid
> - waste, we allocate only the fd/bk pointers of bins, and then use
> - repositioning tricks to treat these as the fields of a chunk.
> -
> - TreeBins
> - Treebins are pointers to the roots of trees holding a range of
> - sizes. There are 2 equally spaced treebins for each power of two
> - from TREE_SHIFT to TREE_SHIFT+16. The last bin holds anything
> - larger.
> -
> - Bin maps
> - There is one bit map for small bins ("smallmap") and one for
> - treebins ("treemap). Each bin sets its bit when non-empty, and
> - clears the bit when empty. Bit operations are then used to avoid
> - bin-by-bin searching -- nearly all "search" is done without ever
> - looking at bins that won't be selected. The bit maps
> - conservatively use 32 bits per map word, even if on 64bit system.
> - For a good description of some of the bit-based techniques used
> - here, see Henry S. Warren Jr's book "Hacker's Delight" (and
> - supplement at http://hackersdelight.org/). Many of these are
> - intended to reduce the branchiness of paths through malloc etc, as
> - well as to reduce the number of memory locations read or written.
> -
> - Segments
> - A list of segments headed by an embedded malloc_segment record
> - representing the initial space.
> -
> - Address check support
> - The least_addr field is the least address ever obtained from
> - MORECORE or MMAP. Attempted frees and reallocs of any address less
> - than this are trapped (unless INSECURE is defined).
> -
> - Magic tag
> - A cross-check field that should always hold same value as mparams.magic.
> -
> - Flags
> - Bits recording whether to use MMAP, locks, or contiguous MORECORE
> -
> - Statistics
> - Each space keeps track of current and maximum system memory
> - obtained via MORECORE or MMAP.
> -
> - Locking
> - If USE_LOCKS is defined, the "mutex" lock is acquired and released
> - around every public call using this mspace.
> -*/
> -
> -/* Bin types, widths and sizes */
> -#define NSMALLBINS (32U)
> -#define NTREEBINS (32U)
> -#define SMALLBIN_SHIFT (3U)
> -#define SMALLBIN_WIDTH (SIZE_T_ONE << SMALLBIN_SHIFT)
> -#define TREEBIN_SHIFT (8U)
> -#define MIN_LARGE_SIZE (SIZE_T_ONE << TREEBIN_SHIFT)
> -#define MAX_SMALL_SIZE (MIN_LARGE_SIZE - SIZE_T_ONE)
> -#define MAX_SMALL_REQUEST (MAX_SMALL_SIZE - CHUNK_ALIGN_MASK -
> CHUNK_OVERHEAD)
> -
> -struct malloc_state {
> - binmap_t smallmap;
> - binmap_t treemap;
> - size_t dvsize;
> - size_t topsize;
> - char* least_addr;
> - mchunkptr dv;
> - mchunkptr top;
> - size_t magic;
> - mchunkptr smallbins[(NSMALLBINS+1)*2];
> - tbinptr treebins[NTREEBINS];
> - size_t footprint;
> - size_t max_footprint;
> - flag_t mflags;
> - void *user_data;
> -#if USE_LOCKS
> - MLOCK_T mutex; /* locate lock among fields that rarely change */
> -#endif /* USE_LOCKS */
> - msegment seg;
> -};
> -
> -typedef struct malloc_state* mstate;
> -
> -/* ------------- Global malloc_state and malloc_params -------------------
> */
> -
> -/*
> - malloc_params holds global properties, including those that can be
> - dynamically set using mallopt. There is a single instance, mparams,
> - initialized in init_mparams.
> -*/
> -
> -struct malloc_params {
> - size_t magic;
> - size_t page_size;
> - size_t granularity;
> - flag_t default_mflags;
> -};
> -
> -static struct malloc_params mparams;
> -
> -/* The global malloc_state used for all non-"mspace" calls */
> -//static struct malloc_state _gm_;
> -//#define gm (&_gm_)
> -//#define is_global(M) ((M) == &_gm_)
> -#define is_initialized(M) ((M)->top != 0)
> -
> -/* -------------------------- system alloc setup -------------------------
> */
> -
> -/* Operations on mflags */
> -
> -#define use_lock(M) ((M)->mflags & USE_LOCK_BIT)
> -#define enable_lock(M) ((M)->mflags |= USE_LOCK_BIT)
> -#define disable_lock(M) ((M)->mflags &= ~USE_LOCK_BIT)
> -
> -#define set_lock(M,L)\
> - ((M)->mflags = (L)?\
> - ((M)->mflags | USE_LOCK_BIT) :\
> - ((M)->mflags & ~USE_LOCK_BIT))
> -
> -/* page-align a size */
> -#define page_align(S)\
> - (((S) + (mparams.page_size)) & ~(mparams.page_size - SIZE_T_ONE))
> -
> -/* granularity-align a size */
> -#define granularity_align(S)\
> - (((S) + (mparams.granularity)) & ~(mparams.granularity - SIZE_T_ONE))
> -
> -#define is_page_aligned(S)\
> - (((size_t)(S) & (mparams.page_size - SIZE_T_ONE)) == 0)
> -#define is_granularity_aligned(S)\
> - (((size_t)(S) & (mparams.granularity - SIZE_T_ONE)) == 0)
> -
> -/* True if segment S holds address A */
> -#define segment_holds(S, A)\
> - ((char*)(A) >= S->base && (char*)(A) < S->base + S->size)
> -
> -/* Return segment holding given address */
> -static msegmentptr segment_holding(mstate m, char* addr) {
> - msegmentptr sp = &m->seg;
> - for (;;) {
> - if (addr >= sp->base && addr < sp->base + sp->size)
> - return sp;
> - if ((sp = sp->next) == 0)
> - return 0;
> - }
> -}
> -
> -/* Return true if segment contains a segment link */
> -static int has_segment_link(mstate m, msegmentptr ss) {
> - msegmentptr sp = &m->seg;
> - for (;;) {
> - if ((char*)sp >= ss->base && (char*)sp < ss->base + ss->size)
> - return 1;
> - if ((sp = sp->next) == 0)
> - return 0;
> - }
> -}
> -
> -
> -
> -/*
> - TOP_FOOT_SIZE is padding at the end of a segment, including space
> - that may be needed to place segment records and fenceposts when new
> - noncontiguous segments are added.
> -*/
> -#define TOP_FOOT_SIZE\
> - (align_offset(chunk2mem(0))+pad_request(sizeof(struct
> malloc_segment))+MIN_CHUNK_SIZE)
> -
> -
> -/* ------------------------------- Hooks --------------------------------
> */
> -
> -/*
> - PREACTION should be defined to return 0 on success, and nonzero on
> - failure. If you are not using locking, you can redefine these to do
> - anything you like.
> -*/
> -
> -#if USE_LOCKS
> -
> -/* Ensure locks are initialized */
> -#define GLOBALLY_INITIALIZE() (mparams.page_size == 0 && init_mparams())
> -
> -#define PREACTION(M) ((GLOBALLY_INITIALIZE() || use_lock(M))?
> ACQUIRE_LOCK(&(M)->mutex) : 0)
> -#define POSTACTION(M) { if (use_lock(M)) RELEASE_LOCK(&(M)->mutex); }
> -#else /* USE_LOCKS */
> -
> -#ifndef PREACTION
> -#define PREACTION(M) (0)
> -#endif /* PREACTION */
> -
> -#ifndef POSTACTION
> -#define POSTACTION(M)
> -#endif /* POSTACTION */
> -
> -#endif /* USE_LOCKS */
> -
> -/*
> - CORRUPTION_ERROR_ACTION is triggered upon detected bad addresses.
> - USAGE_ERROR_ACTION is triggered on detected bad frees and
> - reallocs. The argument p is an address that might have triggered the
> - fault. It is ignored by the two predefined actions, but might be
> - useful in custom actions that try to help diagnose errors.
> -*/
> -
> -#if PROCEED_ON_ERROR
> -
> -/* A count of the number of corruption errors causing resets */
> -int malloc_corruption_error_count;
> -
> -/* default corruption action */
> -static void reset_on_error(mstate m);
> -
> -#define CORRUPTION_ERROR_ACTION(m) reset_on_error(m)
> -#define USAGE_ERROR_ACTION(m, p)
> -
> -#else /* PROCEED_ON_ERROR */
> -
> -#ifndef CORRUPTION_ERROR_ACTION
> -#define CORRUPTION_ERROR_ACTION(m) ABORT(m->user_data)
> -#endif /* CORRUPTION_ERROR_ACTION */
> -
> -#ifndef USAGE_ERROR_ACTION
> -#define USAGE_ERROR_ACTION(m,p) ABORT(m->user_data)
> -#endif /* USAGE_ERROR_ACTION */
> -
> -#endif /* PROCEED_ON_ERROR */
> -
> -/* -------------------------- Debugging setup ----------------------------
> */
> -
> -#if ! DEBUG
> -
> -#define check_free_chunk(M,P)
> -#define check_inuse_chunk(M,P)
> -#define check_malloced_chunk(M,P,N)
> -#define check_malloc_state(M)
> -#define check_top_chunk(M,P)
> -
> -#else /* DEBUG */
> -#define check_free_chunk(M,P) do_check_free_chunk(M,P)
> -#define check_inuse_chunk(M,P) do_check_inuse_chunk(M,P)
> -#define check_top_chunk(M,P) do_check_top_chunk(M,P)
> -#define check_malloced_chunk(M,P,N) do_check_malloced_chunk(M,P,N)
> -#define check_malloc_state(M) do_check_malloc_state(M)
> -
> -static void do_check_any_chunk(mstate m, mchunkptr p);
> -static void do_check_top_chunk(mstate m, mchunkptr p);
> -static void do_check_inuse_chunk(mstate m, mchunkptr p);
> -static void do_check_free_chunk(mstate m, mchunkptr p);
> -static void do_check_malloced_chunk(mstate m, void* mem, size_t s);
> -static void do_check_tree(mstate m, tchunkptr t);
> -static void do_check_treebin(mstate m, bindex_t i);
> -static void do_check_smallbin(mstate m, bindex_t i);
> -static void do_check_malloc_state(mstate m);
> -static int bin_find(mstate m, mchunkptr x);
> -static size_t traverse_and_check(mstate m);
> -#endif /* DEBUG */
> -
> -/* ---------------------------- Indexing Bins ----------------------------
> */
> -
> -#define is_small(s) (((s) >> SMALLBIN_SHIFT) < NSMALLBINS)
> -#define small_index(s) ((s) >> SMALLBIN_SHIFT)
> -#define small_index2size(i) ((i) << SMALLBIN_SHIFT)
> -#define MIN_SMALL_INDEX (small_index(MIN_CHUNK_SIZE))
> -
> -/* addressing by index. See above about smallbin repositioning */
> -#define smallbin_at(M, i) ((sbinptr)((char*)&((M)->smallbins[(i)<<1])))
> -#define treebin_at(M,i) (&((M)->treebins[i]))
> -
> -/* assign tree index for size S to variable I */
> -#if defined(__GNUC__) && defined(i386)
> -#define compute_tree_index(S, I)\
> -{\
> - size_t X = S >> TREEBIN_SHIFT;\
> - if (X == 0)\
> - I = 0;\
> - else if (X > 0xFFFF)\
> - I = NTREEBINS-1;\
> - else {\
> - unsigned int K;\
> - __asm__("bsrl %1,%0\n\t" : "=r" (K) : "rm" (X));\
> - I = (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\
> - }\
> -}
> -#else /* GNUC */
> -#define compute_tree_index(S, I)\
> -{\
> - size_t X = S >> TREEBIN_SHIFT;\
> - if (X == 0)\
> - I = 0;\
> - else if (X > 0xFFFF)\
> - I = NTREEBINS-1;\
> - else {\
> - unsigned int Y = (unsigned int)X;\
> - unsigned int N = ((Y - 0x100) >> 16) & 8;\
> - unsigned int K = (((Y <<= N) - 0x1000) >> 16) & 4;\
> - N += K;\
> - N += K = (((Y <<= K) - 0x4000) >> 16) & 2;\
> - K = 14 - N + ((Y <<= K) >> 15);\
> - I = (K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1));\
> - }\
> -}
> -#endif /* GNUC */
> -
> -/* Bit representing maximum resolved size in a treebin at i */
> -#define bit_for_tree_index(i) \
> - (i == NTREEBINS-1)? (SIZE_T_BITSIZE-1) : (((i) >> 1) + TREEBIN_SHIFT - 2)
> -
> -/* Shift placing maximum resolved bit in a treebin at i as sign bit */
> -#define leftshift_for_tree_index(i) \
> - ((i == NTREEBINS-1)? 0 : \
> - ((SIZE_T_BITSIZE-SIZE_T_ONE) - (((i) >> 1) + TREEBIN_SHIFT - 2)))
> -
> -/* The size of the smallest chunk held in bin with index i */
> -#define minsize_for_tree_index(i) \
> - ((SIZE_T_ONE << (((i) >> 1) + TREEBIN_SHIFT)) | \
> - (((size_t)((i) & SIZE_T_ONE)) << (((i) >> 1) + TREEBIN_SHIFT - 1)))
> -
> -/* ------------------------ Operations on bin maps -----------------------
> */
> -
> -/* bit corresponding to given index */
> -#define idx2bit(i) ((binmap_t)(1) << (i))
> -
> -/* Mark/Clear bits with given index */
> -#define mark_smallmap(M,i) ((M)->smallmap |= idx2bit(i))
> -#define clear_smallmap(M,i) ((M)->smallmap &= ~idx2bit(i))
> -#define smallmap_is_marked(M,i) ((M)->smallmap & idx2bit(i))
> -
> -#define mark_treemap(M,i) ((M)->treemap |= idx2bit(i))
> -#define clear_treemap(M,i) ((M)->treemap &= ~idx2bit(i))
> -#define treemap_is_marked(M,i) ((M)->treemap & idx2bit(i))
> -
> -/* index corresponding to given bit */
> -
> -#if defined(__GNUC__) && defined(i386)
> -#define compute_bit2idx(X, I)\
> -{\
> - unsigned int J;\
> - __asm__("bsfl %1,%0\n\t" : "=r" (J) : "rm" (X));\
> - I = (bindex_t)J;\
> -}
> -
> -#else /* GNUC */
> -#if USE_BUILTIN_FFS
> -#define compute_bit2idx(X, I) I = ffs(X)-1
> -
> -#else /* USE_BUILTIN_FFS */
> -#define compute_bit2idx(X, I)\
> -{\
> - unsigned int Y = X - 1;\
> - unsigned int K = Y >> (16-4) & 16;\
> - unsigned int N = K; Y >>= K;\
> - N += K = Y >> (8-3) & 8; Y >>= K;\
> - N += K = Y >> (4-2) & 4; Y >>= K;\
> - N += K = Y >> (2-1) & 2; Y >>= K;\
> - N += K = Y >> (1-0) & 1; Y >>= K;\
> - I = (bindex_t)(N + Y);\
> -}
> -#endif /* USE_BUILTIN_FFS */
> -#endif /* GNUC */
> -
> -/* isolate the least set bit of a bitmap */
> -#define least_bit(x) ((x) & -(x))
> -
> -/* mask with all bits to left of least bit of x on */
> -#define left_bits(x) ((x<<1) | -(x<<1))
> -
> -/* mask with all bits to left of or equal to least bit of x on */
> -#define same_or_left_bits(x) ((x) | -(x))
> -
> -
> -/* ----------------------- Runtime Check Support -------------------------
> */
> -
> -/*
> - For security, the main invariant is that malloc/free/etc never
> - writes to a static address other than malloc_state, unless static
> - malloc_state itself has been corrupted, which cannot occur via
> - malloc (because of these checks). In essence this means that we
> - believe all pointers, sizes, maps etc held in malloc_state, but
> - check all of those linked or offsetted from other embedded data
> - structures. These checks are interspersed with main code in a way
> - that tends to minimize their run-time cost.
> -
> - When FOOTERS is defined, in addition to range checking, we also
> - verify footer fields of inuse chunks, which can be used guarantee
> - that the mstate controlling malloc/free is intact. This is a
> - streamlined version of the approach described by William Robertson
> - et al in "Run-time Detection of Heap-based Overflows" LISA'03
> - http://www.usenix.org/events/lisa03/tech/robertson.html The footer
> - of an inuse chunk holds the xor of its mstate and a random seed,
> - that is checked upon calls to free() and realloc(). This is
> - (probablistically) unguessable from outside the program, but can be
> - computed by any code successfully malloc'ing any chunk, so does not
> - itself provide protection against code that has already broken
> - security through some other means. Unlike Robertson et al, we
> - always dynamically check addresses of all offset chunks (previous,
> - next, etc). This turns out to be cheaper than relying on hashes.
> -*/
> -
> -#if !INSECURE
> -/* Check if address a is at least as high as any from MORECORE or MMAP */
> -#define ok_address(M, a) ((char*)(a) >= (M)->least_addr)
> -/* Check if address of next chunk n is higher than base chunk p */
> -#define ok_next(p, n) ((char*)(p) < (char*)(n))
> -/* Check if p has its cinuse bit on */
> -#define ok_cinuse(p) cinuse(p)
> -/* Check if p has its pinuse bit on */
> -#define ok_pinuse(p) pinuse(p)
> -
> -#else /* !INSECURE */
> -#define ok_address(M, a) (1)
> -#define ok_next(b, n) (1)
> -#define ok_cinuse(p) (1)
> -#define ok_pinuse(p) (1)
> -#endif /* !INSECURE */
> -
> -#if (FOOTERS && !INSECURE)
> -/* Check if (alleged) mstate m has expected magic field */
> -#define ok_magic(M) ((M)->magic == mparams.magic)
> -#else /* (FOOTERS && !INSECURE) */
> -#define ok_magic(M) (1)
> -#endif /* (FOOTERS && !INSECURE) */
> -
> -
> -/* In gcc, use __builtin_expect to minimize impact of checks */
> -#if !INSECURE
> -#if defined(__GNUC__) && __GNUC__ >= 3
> -#define RTCHECK(e) __builtin_expect(e, 1)
> -#else /* GNUC */
> -#define RTCHECK(e) (e)
> -#endif /* GNUC */
> -#else /* !INSECURE */
> -#define RTCHECK(e) (1)
> -#endif /* !INSECURE */
> -
> -/* macros to set up inuse chunks with or without footers */
> -
> -#if !FOOTERS
> -
> -#define mark_inuse_foot(M,p,s)
> -
> -/* Set cinuse bit and pinuse bit of next chunk */
> -#define set_inuse(M,p,s)\
> - ((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\
> - ((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT)
> -
> -/* Set cinuse and pinuse of this chunk and pinuse of next chunk */
> -#define set_inuse_and_pinuse(M,p,s)\
> - ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
> - ((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT)
> -
> -/* Set size, cinuse and pinuse bit of this chunk */
> -#define set_size_and_pinuse_of_inuse_chunk(M, p, s)\
> - ((p)->head = (s|PINUSE_BIT|CINUSE_BIT))
> -
> -#else /* FOOTERS */
> -
> -/* Set foot of inuse chunk to be xor of mstate and seed */
> -#define mark_inuse_foot(M,p,s)\
> - (((mchunkptr)((char*)(p) + (s)))->prev_foot = ((size_t)(M) ^
> mparams.magic))
> -
> -#define get_mstate_for(p)\
> - ((mstate)(((mchunkptr)((char*)(p) +\
> - (chunksize(p))))->prev_foot ^ mparams.magic))
> -
> -#define set_inuse(M,p,s)\
> - ((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\
> - (((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT), \
> - mark_inuse_foot(M,p,s))
> -
> -#define set_inuse_and_pinuse(M,p,s)\
> - ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
> - (((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT),\
> - mark_inuse_foot(M,p,s))
> -
> -#define set_size_and_pinuse_of_inuse_chunk(M, p, s)\
> - ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
> - mark_inuse_foot(M, p, s))
> -
> -#endif /* !FOOTERS */
> -
> -/* ---------------------------- setting mparams --------------------------
> */
> -
> -/* Initialize mparams */
> -static int init_mparams(void) {
> - if (mparams.page_size == 0) {
> - size_t s;
> -
> - mparams.default_mflags = USE_LOCK_BIT;
> -
> -#if (FOOTERS && !INSECURE)
> - {
> -#if USE_DEV_RANDOM
> - int fd;
> - unsigned char buf[sizeof(size_t)];
> - /* Try to use /dev/urandom, else fall back on using time */
> - if ((fd = open("/dev/urandom", O_RDONLY)) >= 0 &&
> - read(fd, buf, sizeof(buf)) == sizeof(buf)) {
> - s = *((size_t *) buf);
> - close(fd);
> - }
> - else
> -#endif /* USE_DEV_RANDOM */
> - s = (size_t)(time(0) ^ (size_t)0x55555555U);
> -
> - s |= (size_t)8U; /* ensure nonzero */
> - s &= ~(size_t)7U; /* improve chances of fault for bad values */
> -
> - }
> -#else /* (FOOTERS && !INSECURE) */
> - s = (size_t)0x58585858U;
> -#endif /* (FOOTERS && !INSECURE) */
> - ACQUIRE_MAGIC_INIT_LOCK();
> - if (mparams.magic == 0) {
> - mparams.magic = s;
> - /* Set up lock for main malloc area */
> - //INITIAL_LOCK(&gm->mutex);
> - //gm->mflags = mparams.default_mflags;
> - }
> - RELEASE_MAGIC_INIT_LOCK();
> -
> -
> - mparams.page_size = malloc_getpagesize;
> - mparams.granularity = ((DEFAULT_GRANULARITY != 0)?
> - DEFAULT_GRANULARITY : mparams.page_size);
> -
> - /* Sanity-check configuration:
> - size_t must be unsigned and as wide as pointer type.
> - ints must be at least 4 bytes.
> - alignment must be at least 8.
> - Alignment, min chunk size, and page size must all be powers of 2.
> - */
> - if ((sizeof(size_t) != sizeof(char*)) ||
> - (MAX_SIZE_T < MIN_CHUNK_SIZE) ||
> - (sizeof(int) < 4) ||
> - (MALLOC_ALIGNMENT < (size_t)8U) ||
> - ((MALLOC_ALIGNMENT & (MALLOC_ALIGNMENT-SIZE_T_ONE)) != 0) ||
> - ((MCHUNK_SIZE & (MCHUNK_SIZE-SIZE_T_ONE)) != 0) ||
> - ((mparams.granularity & (mparams.granularity-SIZE_T_ONE)) != 0) ||
> - ((mparams.page_size & (mparams.page_size-SIZE_T_ONE)) != 0))
> - ABORT(NULL);
> - }
> - return 0;
> -}
> -
> -/* support for mallopt */
> -static int change_mparam(int param_number, int value) {
> - size_t val = (size_t)value;
> - init_mparams();
> - switch(param_number) {
> - case M_GRANULARITY:
> - if (val >= mparams.page_size && ((val & (val-1)) == 0)) {
> - mparams.granularity = val;
> - return 1;
> - }
> - else
> - return 0;
> - default:
> - return 0;
> - }
> -}
> -
> -#if DEBUG
> -/* ------------------------- Debugging Support ---------------------------
> */
> -
> -/* Check properties of any chunk, whether free, inuse, mmapped etc */
> -static void do_check_any_chunk(mstate m, mchunkptr p) {
> - assert(m->user_data, (is_aligned(chunk2mem(p))) || (p->head ==
> FENCEPOST_HEAD));
> - assert(m->user_data, ok_address(m, p));
> -}
> -
> -/* Check properties of top chunk */
> -static void do_check_top_chunk(mstate m, mchunkptr p) {
> - msegmentptr sp = segment_holding(m, (char*)p);
> - size_t sz = chunksize(p);
> - assert(m->user_data, sp != 0);
> - assert(m->user_data, (is_aligned(chunk2mem(p))) || (p->head ==
> FENCEPOST_HEAD));
> - assert(m->user_data, ok_address(m, p));
> - assert(m->user_data, sz == m->topsize);
> - assert(m->user_data, sz > 0);
> - assert(m->user_data, sz == ((sp->base + sp->size) - (char*)p) -
> TOP_FOOT_SIZE);
> - assert(m->user_data, pinuse(p));
> - assert(m->user_data, !next_pinuse(p));
> -}
> -
> -/* Check properties of inuse chunks */
> -static void do_check_inuse_chunk(mstate m, mchunkptr p) {
> - do_check_any_chunk(m, p);
> - assert(m->user_data, cinuse(p));
> - assert(m->user_data, next_pinuse(p));
> - /* If not pinuse, previous chunk has OK offset */
> - assert(m->user_data, pinuse(p) || next_chunk(prev_chunk(p)) == p);
> -}
> -
> -/* Check properties of free chunks */
> -static void do_check_free_chunk(mstate m, mchunkptr p) {
> - size_t sz = p->head & ~(PINUSE_BIT|CINUSE_BIT);
> - mchunkptr next = chunk_plus_offset(p, sz);
> - do_check_any_chunk(m, p);
> - assert(m->user_data, !cinuse(p));
> - assert(m->user_data, !next_pinuse(p));
> - if (p != m->dv && p != m->top) {
> - if (sz >= MIN_CHUNK_SIZE) {
> - assert(m->user_data, (sz & CHUNK_ALIGN_MASK) == 0);
> - assert(m->user_data, is_aligned(chunk2mem(p)));
> - assert(m->user_data, next->prev_foot == sz);
> - assert(m->user_data, pinuse(p));
> - assert(m->user_data, next == m->top || cinuse(next));
> - assert(m->user_data, p->fd->bk == p);
> - assert(m->user_data, p->bk->fd == p);
> - }
> - else /* markers are always of size SIZE_T_SIZE */
> - assert(m->user_data, sz == SIZE_T_SIZE);
> - }
> -}
> -
> -/* Check properties of malloced chunks at the point they are malloced */
> -static void do_check_malloced_chunk(mstate m, void* mem, size_t s) {
> - if (mem != 0) {
> - mchunkptr p = mem2chunk(mem);
> - size_t sz = p->head & ~(PINUSE_BIT|CINUSE_BIT);
> - do_check_inuse_chunk(m, p);
> - assert(m->user_data, (sz & CHUNK_ALIGN_MASK) == 0);
> - assert(m->user_data, sz >= MIN_CHUNK_SIZE);
> - assert(m->user_data, sz >= s);
> - /* size is less than MIN_CHUNK_SIZE more than request */
> - assert(m->user_data, sz < (s + MIN_CHUNK_SIZE));
> - }
> -}
> -
> -/* Check a tree and its subtrees. */
> -static void do_check_tree(mstate m, tchunkptr t) {
> - tchunkptr head = 0;
> - tchunkptr u = t;
> - bindex_t tindex = t->index;
> - size_t tsize = chunksize(t);
> - bindex_t idx;
> - compute_tree_index(tsize, idx);
> - assert(m->user_data, tindex == idx);
> - assert(m->user_data, tsize >= MIN_LARGE_SIZE);
> - assert(m->user_data, tsize >= minsize_for_tree_index(idx));
> - assert(m->user_data, (idx == NTREEBINS-1) || (tsize <
> minsize_for_tree_index((idx+1))));
> -
> - do { /* traverse through chain of same-sized nodes */
> - do_check_any_chunk(m, ((mchunkptr)u));
> - assert(m->user_data, u->index == tindex);
> - assert(m->user_data, chunksize(u) == tsize);
> - assert(m->user_data, !cinuse(u));
> - assert(m->user_data, !next_pinuse(u));
> - assert(m->user_data, u->fd->bk == u);
> - assert(m->user_data, u->bk->fd == u);
> - if (u->parent == 0) {
> - assert(m->user_data, u->child[0] == 0);
> - assert(m->user_data, u->child[1] == 0);
> - }
> - else {
> - assert(m->user_data, head == 0); /* only one node on chain has parent
> */
> - head = u;
> - assert(m->user_data, u->parent != u);
> - assert(m->user_data, u->parent->child[0] == u ||
> - u->parent->child[1] == u ||
> - *((tbinptr*)(u->parent)) == u);
> - if (u->child[0] != 0) {
> - assert(m->user_data, u->child[0]->parent == u);
> - assert(m->user_data, u->child[0] != u);
> - do_check_tree(m, u->child[0]);
> - }
> - if (u->child[1] != 0) {
> - assert(m->user_data, u->child[1]->parent == u);
> - assert(m->user_data, u->child[1] != u);
> - do_check_tree(m, u->child[1]);
> - }
> - if (u->child[0] != 0 && u->child[1] != 0) {
> - assert(m->user_data, chunksize(u->child[0]) <
> chunksize(u->child[1]));
> - }
> - }
> - u = u->fd;
> - } while (u != t);
> - assert(m->user_data, head != 0);
> -}
> -
> -/* Check all the chunks in a treebin. */
> -static void do_check_treebin(mstate m, bindex_t i) {
> - tbinptr* tb = treebin_at(m, i);
> - tchunkptr t = *tb;
> - int empty = (m->treemap & (1U << i)) == 0;
> - if (t == 0)
> - assert(m->user_data, empty);
> - if (!empty)
> - do_check_tree(m, t);
> -}
> -
> -/* Check all the chunks in a smallbin. */
> -static void do_check_smallbin(mstate m, bindex_t i) {
> - sbinptr b = smallbin_at(m, i);
> - mchunkptr p = b->bk;
> - unsigned int empty = (m->smallmap & (1U << i)) == 0;
> - if (p == b)
> - assert(m->user_data, empty);
> - if (!empty) {
> - for (; p != b; p = p->bk) {
> - size_t size = chunksize(p);
> - mchunkptr q;
> - /* each chunk claims to be free */
> - do_check_free_chunk(m, p);
> - /* chunk belongs in bin */
> - assert(m->user_data, small_index(size) == i);
> - assert(m->user_data, p->bk == b || chunksize(p->bk) == chunksize(p));
> - /* chunk is followed by an inuse chunk */
> - q = next_chunk(p);
> - if (q->head != FENCEPOST_HEAD)
> - do_check_inuse_chunk(m, q);
> - }
> - }
> -}
> -
> -/* Find x in a bin. Used in other check functions. */
> -static int bin_find(mstate m, mchunkptr x) {
> - size_t size = chunksize(x);
> - if (is_small(size)) {
> - bindex_t sidx = small_index(size);
> - sbinptr b = smallbin_at(m, sidx);
> - if (smallmap_is_marked(m, sidx)) {
> - mchunkptr p = b;
> - do {
> - if (p == x)
> - return 1;
> - } while ((p = p->fd) != b);
> - }
> - }
> - else {
> - bindex_t tidx;
> - compute_tree_index(size, tidx);
> - if (treemap_is_marked(m, tidx)) {
> - tchunkptr t = *treebin_at(m, tidx);
> - size_t sizebits = size << leftshift_for_tree_index(tidx);
> - while (t != 0 && chunksize(t) != size) {
> - t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1];
> - sizebits <<= 1;
> - }
> - if (t != 0) {
> - tchunkptr u = t;
> - do {
> - if (u == (tchunkptr)x)
> - return 1;
> - } while ((u = u->fd) != t);
> - }
> - }
> - }
> - return 0;
> -}
> -
> -/* Traverse each chunk and check it; return total */
> -static size_t traverse_and_check(mstate m) {
> - size_t sum = 0;
> - if (is_initialized(m)) {
> - msegmentptr s = &m->seg;
> - sum += m->topsize + TOP_FOOT_SIZE;
> - while (s != 0) {
> - mchunkptr q = align_as_chunk(s->base);
> - mchunkptr lastq = 0;
> - assert(m->user_data, pinuse(q));
> - while (segment_holds(s, q) &&
> - q != m->top && q->head != FENCEPOST_HEAD) {
> - sum += chunksize(q);
> - if (cinuse(q)) {
> - assert(m->user_data, !bin_find(m, q));
> - do_check_inuse_chunk(m, q);
> - }
> - else {
> - assert(m->user_data, q == m->dv || bin_find(m, q));
> - assert(m->user_data, lastq == 0 || cinuse(lastq)); /* Not 2
> consecutive free */
> - do_check_free_chunk(m, q);
> - }
> - lastq = q;
> - q = next_chunk(q);
> - }
> - s = s->next;
> - }
> - }
> - return sum;
> -}
> -
> -/* Check all properties of malloc_state. */
> -static void do_check_malloc_state(mstate m) {
> - bindex_t i;
> - size_t total;
> - /* check bins */
> - for (i = 0; i < NSMALLBINS; ++i)
> - do_check_smallbin(m, i);
> - for (i = 0; i < NTREEBINS; ++i)
> - do_check_treebin(m, i);
> -
> - if (m->dvsize != 0) { /* check dv chunk */
> - do_check_any_chunk(m, m->dv);
> - assert(m->user_data, m->dvsize == chunksize(m->dv));
> - assert(m->user_data, m->dvsize >= MIN_CHUNK_SIZE);
> - assert(m->user_data, bin_find(m, m->dv) == 0);
> - }
> -
> - if (m->top != 0) { /* check top chunk */
> - do_check_top_chunk(m, m->top);
> - assert(m->user_data, m->topsize == chunksize(m->top));
> - assert(m->user_data, m->topsize > 0);
> - assert(m->user_data, bin_find(m, m->top) == 0);
> - }
> -
> - total = traverse_and_check(m);
> - assert(m->user_data, total <= m->footprint);
> - assert(m->user_data, m->footprint <= m->max_footprint);
> -}
> -#endif /* DEBUG */
> -
> -/* ----------------------------- statistics ------------------------------
> */
> -
> -#if !NO_MALLINFO
> -static struct mallinfo internal_mallinfo(mstate m) {
> - struct mallinfo nm = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
> - if (!PREACTION(m)) {
> - check_malloc_state(m);
> - if (is_initialized(m)) {
> - size_t nfree = SIZE_T_ONE; /* top always free */
> - size_t mfree = m->topsize + TOP_FOOT_SIZE;
> - size_t sum = mfree;
> - msegmentptr s = &m->seg;
> - while (s != 0) {
> - mchunkptr q = align_as_chunk(s->base);
> - while (segment_holds(s, q) &&
> - q != m->top && q->head != FENCEPOST_HEAD) {
> - size_t sz = chunksize(q);
> - sum += sz;
> - if (!cinuse(q)) {
> - mfree += sz;
> - ++nfree;
> - }
> - q = next_chunk(q);
> - }
> - s = s->next;
> - }
> -
> - nm.arena = sum;
> - nm.ordblks = nfree;
> - nm.hblkhd = m->footprint - sum;
> - nm.usmblks = m->max_footprint;
> - nm.uordblks = m->footprint - mfree;
> - nm.fordblks = mfree;
> - nm.keepcost = m->topsize;
> - }
> -
> - POSTACTION(m);
> - }
> - return nm;
> -}
> -#endif /* !NO_MALLINFO */
> -
> -static void internal_malloc_stats(mstate m) {
> - if (!PREACTION(m)) {
> - size_t maxfp = 0;
> - size_t fp = 0;
> - size_t used = 0;
> - check_malloc_state(m);
> - if (is_initialized(m)) {
> - msegmentptr s = &m->seg;
> - maxfp = m->max_footprint;
> - fp = m->footprint;
> - used = fp - (m->topsize + TOP_FOOT_SIZE);
> -
> - while (s != 0) {
> - mchunkptr q = align_as_chunk(s->base);
> - while (segment_holds(s, q) &&
> - q != m->top && q->head != FENCEPOST_HEAD) {
> - if (!cinuse(q))
> - used -= chunksize(q);
> - q = next_chunk(q);
> - }
> - s = s->next;
> - }
> - }
> -
> - PRINT((m->user_data, "max system bytes = %10lu\n", (unsigned
> long)(maxfp)));
> - PRINT((m->user_data, "system bytes = %10lu\n", (unsigned
> long)(fp)));
> - PRINT((m->user_data, "in use bytes = %10lu\n", (unsigned
> long)(used)));
> -
> - POSTACTION(m);
> - }
> -}
> -
> -/* ----------------------- Operations on smallbins -----------------------
> */
> -
> -/*
> - Various forms of linking and unlinking are defined as macros. Even
> - the ones for trees, which are very long but have very short typical
> - paths. This is ugly but reduces reliance on inlining support of
> - compilers.
> -*/
> -
> -/* Link a free chunk into a smallbin */
> -#define insert_small_chunk(M, P, S) {\
> - bindex_t I = small_index(S);\
> - mchunkptr B = smallbin_at(M, I);\
> - mchunkptr F = B;\
> - assert((M)->user_data, S >= MIN_CHUNK_SIZE);\
> - if (!smallmap_is_marked(M, I))\
> - mark_smallmap(M, I);\
> - else if (RTCHECK(ok_address(M, B->fd)))\
> - F = B->fd;\
> - else {\
> - CORRUPTION_ERROR_ACTION(M);\
> - }\
> - B->fd = P;\
> - F->bk = P;\
> - P->fd = F;\
> - P->bk = B;\
> -}
> -
> -/* Unlink a chunk from a smallbin */
> -#define unlink_small_chunk(M, P, S) {\
> - mchunkptr F = P->fd;\
> - mchunkptr B = P->bk;\
> - bindex_t I = small_index(S);\
> - assert((M)->user_data, P != B);\
> - assert((M)->user_data, P != F);\
> - assert((M)->user_data, chunksize(P) == small_index2size(I));\
> - if (F == B)\
> - clear_smallmap(M, I);\
> - else if (RTCHECK((F == smallbin_at(M,I) || ok_address(M, F)) &&\
> - (B == smallbin_at(M,I) || ok_address(M, B)))) {\
> - F->bk = B;\
> - B->fd = F;\
> - }\
> - else {\
> - CORRUPTION_ERROR_ACTION(M);\
> - }\
> -}
> -
> -/* Unlink the first chunk from a smallbin */
> -#define unlink_first_small_chunk(M, B, P, I) {\
> - mchunkptr F = P->fd;\
> - assert((M)->user_data, P != B);\
> - assert((M)->user_data, P != F);\
> - assert((M)->user_data, chunksize(P) == small_index2size(I));\
> - if (B == F)\
> - clear_smallmap(M, I);\
> - else if (RTCHECK(ok_address(M, F))) {\
> - B->fd = F;\
> - F->bk = B;\
> - }\
> - else {\
> - CORRUPTION_ERROR_ACTION(M);\
> - }\
> -}
> -
> -/* Replace dv node, binning the old one */
> -/* Used only when dvsize known to be small */
> -#define replace_dv(M, P, S) {\
> - size_t DVS = M->dvsize;\
> - if (DVS != 0) {\
> - mchunkptr DV = M->dv;\
> - assert((M)->user_data, is_small(DVS));\
> - insert_small_chunk(M, DV, DVS);\
> - }\
> - M->dvsize = S;\
> - M->dv = P;\
> -}
> -
> -
> -/* ------------------------- Operations on trees -------------------------
> */
> -
> -/* Insert chunk into tree */
> -#define insert_large_chunk(M, X, S) {\
> - tbinptr* H;\
> - bindex_t I;\
> - compute_tree_index(S, I);\
> - H = treebin_at(M, I);\
> - X->index = I;\
> - X->child[0] = X->child[1] = 0;\
> - if (!treemap_is_marked(M, I)) {\
> - mark_treemap(M, I);\
> - *H = X;\
> - X->parent = (tchunkptr)H;\
> - X->fd = X->bk = X;\
> - }\
> - else {\
> - tchunkptr T = *H;\
> - size_t K = S << leftshift_for_tree_index(I);\
> - for (;;) {\
> - if (chunksize(T) != S) {\
> - tchunkptr* C = &(T->child[(K >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1]);\
> - K <<= 1;\
> - if (*C != 0)\
> - T = *C;\
> - else if (RTCHECK(ok_address(M, C))) {\
> - *C = X;\
> - X->parent = T;\
> - X->fd = X->bk = X;\
> - break;\
> - }\
> - else {\
> - CORRUPTION_ERROR_ACTION(M);\
> - break;\
> - }\
> - }\
> - else {\
> - tchunkptr F = T->fd;\
> - if (RTCHECK(ok_address(M, T) && ok_address(M, F))) {\
> - T->fd = F->bk = X;\
> - X->fd = F;\
> - X->bk = T;\
> - X->parent = 0;\
> - break;\
> - }\
> - else {\
> - CORRUPTION_ERROR_ACTION(M);\
> - break;\
> - }\
> - }\
> - }\
> - }\
> -}
> -
> -/*
> - Unlink steps:
> -
> - 1. If x is a chained node, unlink it from its same-sized fd/bk links
> - and choose its bk node as its replacement.
> - 2. If x was the last node of its size, but not a leaf node, it must
> - be replaced with a leaf node (not merely one with an open left or
> - right), to make sure that lefts and rights of descendents
> - correspond properly to bit masks. We use the rightmost descendent
> - of x. We could use any other leaf, but this is easy to locate and
> - tends to counteract removal of leftmosts elsewhere, and so keeps
> - paths shorter than minimally guaranteed. This doesn't loop much
> - because on average a node in a tree is near the bottom.
> - 3. If x is the base of a chain (i.e., has parent links) relink
> - x's parent and children to x's replacement (or null if none).
> -*/
> -
> -#define unlink_large_chunk(M, X) {\
> - tchunkptr XP = X->parent;\
> - tchunkptr R;\
> - if (X->bk != X) {\
> - tchunkptr F = X->fd;\
> - R = X->bk;\
> - if (RTCHECK(ok_address(M, F))) {\
> - F->bk = R;\
> - R->fd = F;\
> - }\
> - else {\
> - CORRUPTION_ERROR_ACTION(M);\
> - }\
> - }\
> - else {\
> - tchunkptr* RP;\
> - if (((R = *(RP = &(X->child[1]))) != 0) ||\
> - ((R = *(RP = &(X->child[0]))) != 0)) {\
> - tchunkptr* CP;\
> - while ((*(CP = &(R->child[1])) != 0) ||\
> - (*(CP = &(R->child[0])) != 0)) {\
> - R = *(RP = CP);\
> - }\
> - if (RTCHECK(ok_address(M, RP)))\
> - *RP = 0;\
> - else {\
> - CORRUPTION_ERROR_ACTION(M);\
> - }\
> - }\
> - }\
> - if (XP != 0) {\
> - tbinptr* H = treebin_at(M, X->index);\
> - if (X == *H) {\
> - if ((*H = R) == 0) \
> - clear_treemap(M, X->index);\
> - }\
> - else if (RTCHECK(ok_address(M, XP))) {\
> - if (XP->child[0] == X) \
> - XP->child[0] = R;\
> - else \
> - XP->child[1] = R;\
> - }\
> - else\
> - CORRUPTION_ERROR_ACTION(M);\
> - if (R != 0) {\
> - if (RTCHECK(ok_address(M, R))) {\
> - tchunkptr C0, C1;\
> - R->parent = XP;\
> - if ((C0 = X->child[0]) != 0) {\
> - if (RTCHECK(ok_address(M, C0))) {\
> - R->child[0] = C0;\
> - C0->parent = R;\
> - }\
> - else\
> - CORRUPTION_ERROR_ACTION(M);\
> - }\
> - if ((C1 = X->child[1]) != 0) {\
> - if (RTCHECK(ok_address(M, C1))) {\
> - R->child[1] = C1;\
> - C1->parent = R;\
> - }\
> - else\
> - CORRUPTION_ERROR_ACTION(M);\
> - }\
> - }\
> - else\
> - CORRUPTION_ERROR_ACTION(M);\
> - }\
> - }\
> -}
> -
> -/* Relays to large vs small bin operations */
> -
> -#define insert_chunk(M, P, S)\
> - if (is_small(S)) insert_small_chunk(M, P, S)\
> - else { tchunkptr TP = (tchunkptr)(P); insert_large_chunk(M, TP, S); }
> -
> -#define unlink_chunk(M, P, S)\
> - if (is_small(S)) unlink_small_chunk(M, P, S)\
> - else { tchunkptr TP = (tchunkptr)(P); unlink_large_chunk(M, TP); }
> -
> -
> -/* Relays to internal calls to malloc/free from realloc, memalign etc */
> -
> -#define internal_malloc(m, b) mspace_malloc(m, b)
> -#define internal_free(m, mem) mspace_free(m,mem);
> -
> -
> -/* -------------------------- mspace management --------------------------
> */
> -
> -/* Initialize top chunk and its size */
> -static void init_top(mstate m, mchunkptr p, size_t psize) {
> - /* Ensure alignment */
> - size_t offset = align_offset(chunk2mem(p));
> - p = (mchunkptr)((char*)p + offset);
> - psize -= offset;
> -
> - m->top = p;
> - m->topsize = psize;
> - p->head = psize | PINUSE_BIT;
> - /* set size of fake trailing chunk holding overhead space only once */
> - chunk_plus_offset(p, psize)->head = TOP_FOOT_SIZE;
> -}
> -
> -/* Initialize bins for a new mstate that is otherwise zeroed out */
> -static void init_bins(mstate m) {
> - /* Establish circular links for smallbins */
> - bindex_t i;
> - for (i = 0; i < NSMALLBINS; ++i) {
> - sbinptr bin = smallbin_at(m,i);
> - bin->fd = bin->bk = bin;
> - }
> -}
> -
> -#if PROCEED_ON_ERROR
> -
> -/* default corruption action */
> -static void reset_on_error(mstate m) {
> - int i;
> - ++malloc_corruption_error_count;
> - /* Reinitialize fields to forget about all memory */
> - m->smallbins = m->treebins = 0;
> - m->dvsize = m->topsize = 0;
> - m->seg.base = 0;
> - m->seg.size = 0;
> - m->seg.next = 0;
> - m->top = m->dv = 0;
> - for (i = 0; i < NTREEBINS; ++i)
> - *treebin_at(m, i) = 0;
> - init_bins(m);
> -}
> -#endif /* PROCEED_ON_ERROR */
> -
> -/* Allocate chunk and prepend remainder with chunk in successor base. */
> -static void* prepend_alloc(mstate m, char* newbase, char* oldbase,
> - size_t nb) {
> - mchunkptr p = align_as_chunk(newbase);
> - mchunkptr oldfirst = align_as_chunk(oldbase);
> - size_t psize = (char*)oldfirst - (char*)p;
> - mchunkptr q = chunk_plus_offset(p, nb);
> - size_t qsize = psize - nb;
> - set_size_and_pinuse_of_inuse_chunk(m, p, nb);
> -
> - assert(m->user_data, (char*)oldfirst > (char*)q);
> - assert(m->user_data, pinuse(oldfirst));
> - assert(m->user_data, qsize >= MIN_CHUNK_SIZE);
> -
> - /* consolidate remainder with first chunk of old base */
> - if (oldfirst == m->top) {
> - size_t tsize = m->topsize += qsize;
> - m->top = q;
> - q->head = tsize | PINUSE_BIT;
> - check_top_chunk(m, q);
> - }
> - else if (oldfirst == m->dv) {
> - size_t dsize = m->dvsize += qsize;
> - m->dv = q;
> - set_size_and_pinuse_of_free_chunk(q, dsize);
> - }
> - else {
> - if (!cinuse(oldfirst)) {
> - size_t nsize = chunksize(oldfirst);
> - unlink_chunk(m, oldfirst, nsize);
> - oldfirst = chunk_plus_offset(oldfirst, nsize);
> - qsize += nsize;
> - }
> - set_free_with_pinuse(q, qsize, oldfirst);
> - insert_chunk(m, q, qsize);
> - check_free_chunk(m, q);
> - }
> -
> - check_malloced_chunk(m, chunk2mem(p), nb);
> - return chunk2mem(p);
> -}
> -
> -/* -------------------------- System allocation --------------------------
> */
> -
> -/* Get memory from system using MORECORE or MMAP */
> -static void* sys_alloc(mstate m, size_t nb) {
> - MALLOC_FAILURE_ACTION;
> - return 0;
> -}
> -
> -/* ---------------------------- malloc support ---------------------------
> */
> -
> -/* allocate a large request from the best fitting chunk in a treebin */
> -static void* tmalloc_large(mstate m, size_t nb) {
> - tchunkptr v = 0;
> - size_t rsize = -nb; /* Unsigned negation */
> - tchunkptr t;
> - bindex_t idx;
> - compute_tree_index(nb, idx);
> -
> - if ((t = *treebin_at(m, idx)) != 0) {
> - /* Traverse tree for this bin looking for node with size == nb */
> - size_t sizebits = nb << leftshift_for_tree_index(idx);
> - tchunkptr rst = 0; /* The deepest untaken right subtree */
> - for (;;) {
> - tchunkptr rt;
> - size_t trem = chunksize(t) - nb;
> - if (trem < rsize) {
> - v = t;
> - if ((rsize = trem) == 0)
> - break;
> - }
> - rt = t->child[1];
> - t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1];
> - if (rt != 0 && rt != t)
> - rst = rt;
> - if (t == 0) {
> - t = rst; /* set t to least subtree holding sizes > nb */
> - break;
> - }
> - sizebits <<= 1;
> - }
> - }
> -
> - if (t == 0 && v == 0) { /* set t to root of next non-empty treebin */
> - binmap_t leftbits = left_bits(idx2bit(idx)) & m->treemap;
> - if (leftbits != 0) {
> - bindex_t i;
> - binmap_t leastbit = least_bit(leftbits);
> - compute_bit2idx(leastbit, i);
> - t = *treebin_at(m, i);
> - }
> - }
> -
> - while (t != 0) { /* find smallest of tree or subtree */
> - size_t trem = chunksize(t) - nb;
> - if (trem < rsize) {
> - rsize = trem;
> - v = t;
> - }
> - t = leftmost_child(t);
> - }
> -
> - /* If dv is a better fit, return 0 so malloc will use it */
> - if (v != 0 && rsize < (size_t)(m->dvsize - nb)) {
> - if (RTCHECK(ok_address(m, v))) { /* split */
> - mchunkptr r = chunk_plus_offset(v, nb);
> - assert(m->user_data, chunksize(v) == rsize + nb);
> - if (RTCHECK(ok_next(v, r))) {
> - unlink_large_chunk(m, v);
> - if (rsize < MIN_CHUNK_SIZE)
> - set_inuse_and_pinuse(m, v, (rsize + nb));
> - else {
> - set_size_and_pinuse_of_inuse_chunk(m, v, nb);
> - set_size_and_pinuse_of_free_chunk(r, rsize);
> - insert_chunk(m, r, rsize);
> - }
> - return chunk2mem(v);
> - }
> - }
> - CORRUPTION_ERROR_ACTION(m);
> - }
> - return 0;
> -}
> -
> -/* allocate a small request from the best fitting chunk in a treebin */
> -static void* tmalloc_small(mstate m, size_t nb) {
> - tchunkptr t, v;
> - size_t rsize;
> - bindex_t i;
> - binmap_t leastbit = least_bit(m->treemap);
> - compute_bit2idx(leastbit, i);
> -
> - v = t = *treebin_at(m, i);
> - rsize = chunksize(t) - nb;
> -
> - while ((t = leftmost_child(t)) != 0) {
> - size_t trem = chunksize(t) - nb;
> - if (trem < rsize) {
> - rsize = trem;
> - v = t;
> - }
> - }
> -
> - if (RTCHECK(ok_address(m, v))) {
> - mchunkptr r = chunk_plus_offset(v, nb);
> - assert(m->user_data, chunksize(v) == rsize + nb);
> - if (RTCHECK(ok_next(v, r))) {
> - unlink_large_chunk(m, v);
> - if (rsize < MIN_CHUNK_SIZE)
> - set_inuse_and_pinuse(m, v, (rsize + nb));
> - else {
> - set_size_and_pinuse_of_inuse_chunk(m, v, nb);
> - set_size_and_pinuse_of_free_chunk(r, rsize);
> - replace_dv(m, r, rsize);
> - }
> - return chunk2mem(v);
> - }
> - }
> -
> - CORRUPTION_ERROR_ACTION(m);
> - return 0;
> -}
> -
> -/* --------------------------- realloc support ---------------------------
> */
> -
> -static void* internal_realloc(mstate m, void* oldmem, size_t bytes) {
> - if (bytes >= MAX_REQUEST) {
> - MALLOC_FAILURE_ACTION;
> - return 0;
> - }
> - if (!PREACTION(m)) {
> - mchunkptr oldp = mem2chunk(oldmem);
> - size_t oldsize = chunksize(oldp);
> - mchunkptr next = chunk_plus_offset(oldp, oldsize);
> - mchunkptr newp = 0;
> - void* extra = 0;
> -
> - /* Try to either shrink or extend into top. Else malloc-copy-free */
> -
> - if (RTCHECK(ok_address(m, oldp) && ok_cinuse(oldp) &&
> - ok_next(oldp, next) && ok_pinuse(next))) {
> - size_t nb = request2size(bytes);
> - if (oldsize >= nb) { /* already big enough */
> - size_t rsize = oldsize - nb;
> - newp = oldp;
> - if (rsize >= MIN_CHUNK_SIZE) {
> - mchunkptr remainder = chunk_plus_offset(newp, nb);
> - set_inuse(m, newp, nb);
> - set_inuse(m, remainder, rsize);
> - extra = chunk2mem(remainder);
> - }
> - }
> - else if (next == m->top && oldsize + m->topsize > nb) {
> - /* Expand into top */
> - size_t newsize = oldsize + m->topsize;
> - size_t newtopsize = newsize - nb;
> - mchunkptr newtop = chunk_plus_offset(oldp, nb);
> - set_inuse(m, oldp, nb);
> - newtop->head = newtopsize |PINUSE_BIT;
> - m->top = newtop;
> - m->topsize = newtopsize;
> - newp = oldp;
> - }
> - }
> - else {
> - USAGE_ERROR_ACTION(m, oldmem);
> - POSTACTION(m);
> - return 0;
> - }
> -
> - POSTACTION(m);
> -
> - if (newp != 0) {
> - if (extra != 0) {
> - internal_free(m, extra);
> - }
> - check_inuse_chunk(m, newp);
> - return chunk2mem(newp);
> - }
> - else {
> - void* newmem = internal_malloc(m, bytes);
> - if (newmem != 0) {
> - size_t oc = oldsize - overhead_for(oldp);
> - MEMCPY(newmem, oldmem, (oc < bytes)? oc : bytes);
> - internal_free(m, oldmem);
> - }
> - return newmem;
> - }
> - }
> - return 0;
> -}
> -
> -/* --------------------------- memalign support --------------------------
> */
> -
> -static void* internal_memalign(mstate m, size_t alignment, size_t bytes) {
> - if (alignment <= MALLOC_ALIGNMENT) /* Can just use malloc */
> - return internal_malloc(m, bytes);
> - if (alignment < MIN_CHUNK_SIZE) /* must be at least a minimum chunk size
> */
> - alignment = MIN_CHUNK_SIZE;
> - if ((alignment & (alignment-SIZE_T_ONE)) != 0) {/* Ensure a power of 2 */
> - size_t a = MALLOC_ALIGNMENT << 1;
> - while (a < alignment) a <<= 1;
> - alignment = a;
> - }
> -
> - if (bytes >= MAX_REQUEST - alignment) {
> - if (m != 0) { /* Test isn't needed but avoids compiler warning */
> - MALLOC_FAILURE_ACTION;
> - }
> - }
> - else {
> - size_t nb = request2size(bytes);
> - size_t req = nb + alignment + MIN_CHUNK_SIZE - CHUNK_OVERHEAD;
> - char* mem = (char*)internal_malloc(m, req);
> - if (mem != 0) {
> - void* leader = 0;
> - void* trailer = 0;
> - mchunkptr p = mem2chunk(mem);
> -
> - if (PREACTION(m)) return 0;
> - if ((((size_t)(mem)) % alignment) != 0) { /* misaligned */
> - /*
> - Find an aligned spot inside chunk. Since we need to give
> - back leading space in a chunk of at least MIN_CHUNK_SIZE, if
> - the first calculation places us at a spot with less than
> - MIN_CHUNK_SIZE leader, we can move to the next aligned spot.
> - We've allocated enough total room so that this is always
> - possible.
> - */
> - char* br = (char*)mem2chunk((size_t)(((size_t)(mem +
> - alignment -
> - SIZE_T_ONE)) &
> - -alignment));
> - char* pos = ((size_t)(br - (char*)(p)) >= MIN_CHUNK_SIZE)?
> - br : br+alignment;
> - mchunkptr newp = (mchunkptr)pos;
> - size_t leadsize = pos - (char*)(p);
> - size_t newsize = chunksize(p) - leadsize;
> -
> - /* Otherwise, give back leader, use the rest */
> - set_inuse(m, newp, newsize);
> - set_inuse(m, p, leadsize);
> - leader = chunk2mem(p);
> -
> - p = newp;
> - }
> -
> - assert(m->user_data, chunksize(p) >= nb);
> - assert(m->user_data, (((size_t)(chunk2mem(p))) % alignment) == 0);
> - check_inuse_chunk(m, p);
> - POSTACTION(m);
> - if (leader != 0) {
> - internal_free(m, leader);
> - }
> - if (trailer != 0) {
> - internal_free(m, trailer);
> - }
> - return chunk2mem(p);
> - }
> - }
> - return 0;
> -}
> -
> -/* ----------------------------- user mspaces ----------------------------
> */
> -
> -static mstate init_user_mstate(char* tbase, size_t tsize, void *user_data) {
> - size_t msize = pad_request(sizeof(struct malloc_state));
> - mchunkptr mn;
> - mchunkptr msp = align_as_chunk(tbase);
> - mstate m = (mstate)(chunk2mem(msp));
> - MEMCLEAR(m, msize);
> - INITIAL_LOCK(&m->mutex);
> - msp->head = (msize|PINUSE_BIT|CINUSE_BIT);
> - m->seg.base = m->least_addr = tbase;
> - m->seg.size = m->footprint = m->max_footprint = tsize;
> - m->magic = mparams.magic;
> - m->mflags = mparams.default_mflags;
> - m->user_data = user_data;
> - init_bins(m);
> - mn = next_chunk(mem2chunk(m));
> - init_top(m, mn, (size_t)((tbase + tsize) - (char*)mn) - TOP_FOOT_SIZE);
> - check_top_chunk(m, m->top);
> - return m;
> -}
> -
> -mspace create_mspace_with_base(void* base, size_t capacity, int locked, void
> *user_data) {
> - mstate m = 0;
> - size_t msize = pad_request(sizeof(struct malloc_state));
> - init_mparams(); /* Ensure pagesize etc initialized */
> -
> - if (capacity > msize + TOP_FOOT_SIZE &&
> - capacity < (size_t) -(msize + TOP_FOOT_SIZE + mparams.page_size)) {
> - m = init_user_mstate((char*)base, capacity, user_data);
> - set_lock(m, locked);
> - }
> - return (mspace)m;
> -}
> -
> -/*
> - mspace versions of routines are near-clones of the global
> - versions. This is not so nice but better than the alternatives.
> -*/
> -
> -
> -void* mspace_malloc(mspace msp, size_t bytes) {
> - mstate ms = (mstate)msp;
> - if (!ok_magic(ms)) {
> - USAGE_ERROR_ACTION(ms,ms);
> - return 0;
> - }
> - if (!PREACTION(ms)) {
> - void* mem;
> - size_t nb;
> - if (bytes <= MAX_SMALL_REQUEST) {
> - bindex_t idx;
> - binmap_t smallbits;
> - nb = (bytes < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(bytes);
> - idx = small_index(nb);
> - smallbits = ms->smallmap >> idx;
> -
> - if ((smallbits & 0x3U) != 0) { /* Remainderless fit to a smallbin. */
> - mchunkptr b, p;
> - idx += ~smallbits & 1; /* Uses next bin if idx empty */
> - b = smallbin_at(ms, idx);
> - p = b->fd;
> - assert(ms->user_data, chunksize(p) == small_index2size(idx));
> - unlink_first_small_chunk(ms, b, p, idx);
> - set_inuse_and_pinuse(ms, p, small_index2size(idx));
> - mem = chunk2mem(p);
> - check_malloced_chunk(ms, mem, nb);
> - goto postaction;
> - }
> -
> - else if (nb > ms->dvsize) {
> - if (smallbits != 0) { /* Use chunk in next nonempty smallbin */
> - mchunkptr b, p, r;
> - size_t rsize;
> - bindex_t i;
> - binmap_t leftbits = (smallbits << idx) & left_bits(idx2bit(idx));
> - binmap_t leastbit = least_bit(leftbits);
> - compute_bit2idx(leastbit, i);
> - b = smallbin_at(ms, i);
> - p = b->fd;
> - assert(ms->user_data, chunksize(p) == small_index2size(i));
> - unlink_first_small_chunk(ms, b, p, i);
> - rsize = small_index2size(i) - nb;
> - /* Fit here cannot be remainderless if 4byte sizes */
> - if (SIZE_T_SIZE != 4 && rsize < MIN_CHUNK_SIZE)
> - set_inuse_and_pinuse(ms, p, small_index2size(i));
> - else {
> - set_size_and_pinuse_of_inuse_chunk(ms, p, nb);
> - r = chunk_plus_offset(p, nb);
> - set_size_and_pinuse_of_free_chunk(r, rsize);
> - replace_dv(ms, r, rsize);
> - }
> - mem = chunk2mem(p);
> - check_malloced_chunk(ms, mem, nb);
> - goto postaction;
> - }
> -
> - else if (ms->treemap != 0 && (mem = tmalloc_small(ms, nb)) != 0) {
> - check_malloced_chunk(ms, mem, nb);
> - goto postaction;
> - }
> - }
> - }
> - else if (bytes >= MAX_REQUEST)
> - nb = MAX_SIZE_T; /* Too big to allocate. Force failure (in sys alloc)
> */
> - else {
> - nb = pad_request(bytes);
> - if (ms->treemap != 0 && (mem = tmalloc_large(ms, nb)) != 0) {
> - check_malloced_chunk(ms, mem, nb);
> - goto postaction;
> - }
> - }
> -
> - if (nb <= ms->dvsize) {
> - size_t rsize = ms->dvsize - nb;
> - mchunkptr p = ms->dv;
> - if (rsize >= MIN_CHUNK_SIZE) { /* split dv */
> - mchunkptr r = ms->dv = chunk_plus_offset(p, nb);
> - ms->dvsize = rsize;
> - set_size_and_pinuse_of_free_chunk(r, rsize);
> - set_size_and_pinuse_of_inuse_chunk(ms, p, nb);
> - }
> - else { /* exhaust dv */
> - size_t dvs = ms->dvsize;
> - ms->dvsize = 0;
> - ms->dv = 0;
> - set_inuse_and_pinuse(ms, p, dvs);
> - }
> - mem = chunk2mem(p);
> - check_malloced_chunk(ms, mem, nb);
> - goto postaction;
> - }
> -
> - else if (nb < ms->topsize) { /* Split top */
> - size_t rsize = ms->topsize -= nb;
> - mchunkptr p = ms->top;
> - mchunkptr r = ms->top = chunk_plus_offset(p, nb);
> - r->head = rsize | PINUSE_BIT;
> - set_size_and_pinuse_of_inuse_chunk(ms, p, nb);
> - mem = chunk2mem(p);
> - check_top_chunk(ms, ms->top);
> - check_malloced_chunk(ms, mem, nb);
> - goto postaction;
> - }
> -
> - mem = sys_alloc(ms, nb);
> -
> - postaction:
> - POSTACTION(ms);
> - return mem;
> - }
> -
> - return 0;
> -}
> -
> -void mspace_free(mspace msp, void* mem) {
> - if (mem != 0) {
> - mchunkptr p = mem2chunk(mem);
> -#if FOOTERS
> - mstate fm = get_mstate_for(p);
> -#else /* FOOTERS */
> - mstate fm = (mstate)msp;
> -#endif /* FOOTERS */
> - if (!ok_magic(fm)) {
> - USAGE_ERROR_ACTION(fm, p);
> - return;
> - }
> - if (!PREACTION(fm)) {
> - check_inuse_chunk(fm, p);
> - if (RTCHECK(ok_address(fm, p) && ok_cinuse(p))) {
> - size_t psize = chunksize(p);
> - mchunkptr next = chunk_plus_offset(p, psize);
> - if (!pinuse(p)) {
> - size_t prevsize = p->prev_foot;
> -
> - mchunkptr prev = chunk_minus_offset(p, prevsize);
> - psize += prevsize;
> - p = prev;
> - if (RTCHECK(ok_address(fm, prev))) { /* consolidate backward */
> - if (p != fm->dv) {
> - unlink_chunk(fm, p, prevsize);
> - }
> - else if ((next->head & INUSE_BITS) == INUSE_BITS) {
> - fm->dvsize = psize;
> - set_free_with_pinuse(p, psize, next);
> - goto postaction;
> - }
> - }
> - else
> - goto erroraction;
> - }
> -
> - if (RTCHECK(ok_next(p, next) && ok_pinuse(next))) {
> - if (!cinuse(next)) { /* consolidate forward */
> - if (next == fm->top) {
> - size_t tsize = fm->topsize += psize;
> - fm->top = p;
> - p->head = tsize | PINUSE_BIT;
> - if (p == fm->dv) {
> - fm->dv = 0;
> - fm->dvsize = 0;
> - }
> - goto postaction;
> - }
> - else if (next == fm->dv) {
> - size_t dsize = fm->dvsize += psize;
> - fm->dv = p;
> - set_size_and_pinuse_of_free_chunk(p, dsize);
> - goto postaction;
> - }
> - else {
> - size_t nsize = chunksize(next);
> - psize += nsize;
> - unlink_chunk(fm, next, nsize);
> - set_size_and_pinuse_of_free_chunk(p, psize);
> - if (p == fm->dv) {
> - fm->dvsize = psize;
> - goto postaction;
> - }
> - }
> - }
> - else
> - set_free_with_pinuse(p, psize, next);
> - insert_chunk(fm, p, psize);
> - check_free_chunk(fm, p);
> - goto postaction;
> - }
> - }
> - erroraction:
> - USAGE_ERROR_ACTION(fm, p);
> - postaction:
> - POSTACTION(fm);
> - }
> - }
> -}
> -
> -void* mspace_calloc(mspace msp, size_t n_elements, size_t elem_size) {
> - void* mem;
> - size_t req = 0;
> - mstate ms = (mstate)msp;
> - if (!ok_magic(ms)) {
> - USAGE_ERROR_ACTION(ms,ms);
> - return 0;
> - }
> - if (n_elements != 0) {
> - req = n_elements * elem_size;
> - if (((n_elements | elem_size) & ~(size_t)0xffff) &&
> - (req / n_elements != elem_size))
> - req = MAX_SIZE_T; /* force downstream failure on overflow */
> - }
> - mem = internal_malloc(ms, req);
> - if (mem != 0 && calloc_must_clear(mem2chunk(mem)))
> - MEMCLEAR(mem, req);
> - return mem;
> -}
> -
> -void* mspace_realloc(mspace msp, void* oldmem, size_t bytes) {
> - if (oldmem == 0)
> - return mspace_malloc(msp, bytes);
> -#ifdef REALLOC_ZERO_BYTES_FREES
> - if (bytes == 0) {
> - mspace_free(msp, oldmem);
> - return 0;
> - }
> -#endif /* REALLOC_ZERO_BYTES_FREES */
> - else {
> -#if FOOTERS
> - mchunkptr p = mem2chunk(oldmem);
> - mstate ms = get_mstate_for(p);
> -#else /* FOOTERS */
> - mstate ms = (mstate)msp;
> -#endif /* FOOTERS */
> - if (!ok_magic(ms)) {
> - USAGE_ERROR_ACTION(ms,ms);
> - return 0;
> - }
> - return internal_realloc(ms, oldmem, bytes);
> - }
> -}
> -
> -void* mspace_memalign(mspace msp, size_t alignment, size_t bytes) {
> - mstate ms = (mstate)msp;
> - if (!ok_magic(ms)) {
> - USAGE_ERROR_ACTION(ms,ms);
> - return 0;
> - }
> - return internal_memalign(ms, alignment, bytes);
> -}
> -
> -void mspace_malloc_stats(mspace msp) {
> - mstate ms = (mstate)msp;
> - if (ok_magic(ms)) {
> - internal_malloc_stats(ms);
> - }
> - else {
> - USAGE_ERROR_ACTION(ms,ms);
> - }
> -}
> -
> -size_t mspace_footprint(mspace msp) {
> - size_t result;
> - mstate ms = (mstate)msp;
> - if (ok_magic(ms)) {
> - result = ms->footprint;
> - } else {
> - USAGE_ERROR_ACTION(ms,ms);
> - }
> - return result;
> -}
> -
> -
> -size_t mspace_max_footprint(mspace msp) {
> - size_t result;
> - mstate ms = (mstate)msp;
> - if (ok_magic(ms)) {
> - result = ms->max_footprint;
> - } else {
> - USAGE_ERROR_ACTION(ms,ms);
> - }
> - return result;
> -}
> -
> -
> -#if !NO_MALLINFO
> -struct mallinfo mspace_mallinfo(mspace msp) {
> - mstate ms = (mstate)msp;
> - if (!ok_magic(ms)) {
> - USAGE_ERROR_ACTION(ms,ms);
> - }
> - return internal_mallinfo(ms);
> -}
> -#endif /* NO_MALLINFO */
> -
> -int mspace_mallopt(int param_number, int value) {
> - return change_mparam(param_number, value);
> -}
> -
> diff --git a/qxldod/mspace.cpp b/qxldod/mspace.cpp
> new file mode 100755
> index 0000000..d0ba123
> --- /dev/null
> +++ b/qxldod/mspace.cpp
> @@ -0,0 +1,2437 @@
> +// based on dlmalloc from Doug Lea
> +
> +
> +// quote from the Doug Lea original file
> + /*
> + This is a version (aka dlmalloc) of malloc/free/realloc written by
> + Doug Lea and released to the public domain, as explained at
> + http://creativecommons.org/licenses/publicdomain. Send questions,
> + comments, complaints, performance data, etc to dl at cs.oswego.edu
> +
> + * Version 2.8.3 Thu Sep 22 11:16:15 2005 Doug Lea (dl at gee)
> +
> + Note: There may be an updated version of this malloc obtainable at
> + ftp://gee.cs.oswego.edu/pub/misc/malloc.c
> + Check before installing!
> + */
> +
> +
> +#include <ntddk.h>
> +
> +#include "mspace.h"
> +
> +#pragma warning( disable : 4146 ) /* no "unsigned" warnings */
> +
> +#define MALLOC_ALIGNMENT ((size_t)8U)
> +#define USE_LOCKS 0
> +#define malloc_getpagesize ((size_t)4096U)
> +#define DEFAULT_GRANULARITY malloc_getpagesize
> +#define MAX_SIZE_T (~(size_t)0)
> +#define MALLOC_FAILURE_ACTION
> +#define MALLINFO_FIELD_TYPE size_t
> +#define FOOTERS 0
> +#define INSECURE 0
> +#define PROCEED_ON_ERROR 0
> +#define DEBUG 0
> +#define ABORT_ON_ASSERT_FAILURE 1
> +#define ABORT(user_data) abort_func(user_data)
> +#define USE_BUILTIN_FFS 0
> +#define USE_DEV_RANDOM 0
> +#define PRINT(params) print_func params
> +
> +
> +#define MEMCPY(dest, src, n) RtlCopyMemory(dest, src, n)
> +#define MEMCLEAR(dest, n) RtlZeroMemory(dest, n)
> +
> +
> +#define M_GRANULARITY (-1)
> +
> +void default_abort_func(void *user_data)
> +{
> + for (;;);
> +}
> +
> +void default_print_func(void *user_data, char *format, ...)
> +{
> +}
> +
> +static mspace_abort_t abort_func = default_abort_func;
> +static mspace_print_t print_func = default_print_func;
> +
> +void mspace_set_abort_func(mspace_abort_t f)
> +{
> + abort_func = f;
> +}
> +
> +void mspace_set_print_func(mspace_print_t f)
> +{
> + print_func = f;
> +}
> +
> +/* ------------------------ Mallinfo declarations ------------------------
> */
> +
> +#if !NO_MALLINFO
> +/*
> + This version of malloc supports the standard SVID/XPG mallinfo
> + routine that returns a struct containing usage properties and
> + statistics. It should work on any system that has a
> + /usr/include/malloc.h defining struct mallinfo. The main
> + declaration needed is the mallinfo struct that is returned (by-copy)
> + by mallinfo(). The malloinfo struct contains a bunch of fields that
> + are not even meaningful in this version of malloc. These fields are
> + are instead filled by mallinfo() with other numbers that might be of
> + interest.
> +
> + HAVE_USR_INCLUDE_MALLOC_H should be set if you have a
> + /usr/include/malloc.h file that includes a declaration of struct
> + mallinfo. If so, it is included; else a compliant version is
> + declared below. These must be precisely the same for mallinfo() to
> + work. The original SVID version of this struct, defined on most
> + systems with mallinfo, declares all fields as ints. But some others
> + define as unsigned long. If your system defines the fields using a
> + type of different width than listed here, you MUST #include your
> + system version and #define HAVE_USR_INCLUDE_MALLOC_H.
> +*/
> +
> +/* #define HAVE_USR_INCLUDE_MALLOC_H */
> +
> +
> +struct mallinfo {
> + MALLINFO_FIELD_TYPE arena; /* non-mmapped space allocated from system
> */
> + MALLINFO_FIELD_TYPE ordblks; /* number of free chunks */
> + MALLINFO_FIELD_TYPE smblks; /* always 0 */
> + MALLINFO_FIELD_TYPE hblks; /* always 0 */
> + MALLINFO_FIELD_TYPE hblkhd; /* space in mmapped regions */
> + MALLINFO_FIELD_TYPE usmblks; /* maximum total allocated space */
> + MALLINFO_FIELD_TYPE fsmblks; /* always 0 */
> + MALLINFO_FIELD_TYPE uordblks; /* total allocated space */
> + MALLINFO_FIELD_TYPE fordblks; /* total free space */
> + MALLINFO_FIELD_TYPE keepcost; /* releasable (via malloc_trim) space */
> +};
> +
> +#endif /* NO_MALLINFO */
> +
> +
> +
> +#ifdef DEBUG
> +#if ABORT_ON_ASSERT_FAILURE
> +#define assert(user_data, x) if(!(x)) ABORT(user_data)
> +#else /* ABORT_ON_ASSERT_FAILURE */
> +#include <assert.h>
> +#endif /* ABORT_ON_ASSERT_FAILURE */
> +#else /* DEBUG */
> +#define assert(user_data, x)
> +#endif /* DEBUG */
> +
> +/* ------------------- size_t and alignment properties --------------------
> */
> +
> +/* The byte and bit size of a size_t */
> +#define SIZE_T_SIZE (sizeof(size_t))
> +#define SIZE_T_BITSIZE (sizeof(size_t) << 3)
> +
> +/* Some constants coerced to size_t */
> +/* Annoying but necessary to avoid errors on some plaftorms */
> +#define SIZE_T_ZERO ((size_t)0)
> +#define SIZE_T_ONE ((size_t)1)
> +#define SIZE_T_TWO ((size_t)2)
> +#define TWO_SIZE_T_SIZES (SIZE_T_SIZE<<1)
> +#define FOUR_SIZE_T_SIZES (SIZE_T_SIZE<<2)
> +#define SIX_SIZE_T_SIZES (FOUR_SIZE_T_SIZES+TWO_SIZE_T_SIZES)
> +#define HALF_MAX_SIZE_T (MAX_SIZE_T / 2U)
> +
> +/* The bit mask value corresponding to MALLOC_ALIGNMENT */
> +#define CHUNK_ALIGN_MASK (MALLOC_ALIGNMENT - SIZE_T_ONE)
> +
> +/* True if address a has acceptable alignment */
> +#define is_aligned(A) (((size_t)((A)) & (CHUNK_ALIGN_MASK)) == 0)
> +
> +/* the number of bytes to offset an address to align it */
> +#define align_offset(A)\
> + ((((size_t)(A) & CHUNK_ALIGN_MASK) == 0)? 0 :\
> + ((MALLOC_ALIGNMENT - ((size_t)(A) & CHUNK_ALIGN_MASK)) &
> CHUNK_ALIGN_MASK))
> +
> +/* --------------------------- Lock preliminaries ------------------------
> */
> +
> +#if USE_LOCKS
> +
> +/*
> + When locks are defined, there are up to two global locks:
> +
> + * If HAVE_MORECORE, morecore_mutex protects sequences of calls to
> + MORECORE. In many cases sys_alloc requires two calls, that should
> + not be interleaved with calls by other threads. This does not
> + protect against direct calls to MORECORE by other threads not
> + using this lock, so there is still code to cope the best we can on
> + interference.
> +
> + * magic_init_mutex ensures that mparams.magic and other
> + unique mparams values are initialized only once.
> +*/
> +
> +
> +#define USE_LOCK_BIT (2U)
> +#else /* USE_LOCKS */
> +#define USE_LOCK_BIT (0U)
> +#define INITIAL_LOCK(l)
> +#endif /* USE_LOCKS */
> +
> +#if USE_LOCKS
> +#define ACQUIRE_MAGIC_INIT_LOCK() ACQUIRE_LOCK(&magic_init_mutex);
> +#define RELEASE_MAGIC_INIT_LOCK() RELEASE_LOCK(&magic_init_mutex);
> +#else /* USE_LOCKS */
> +#define ACQUIRE_MAGIC_INIT_LOCK()
> +#define RELEASE_MAGIC_INIT_LOCK()
> +#endif /* USE_LOCKS */
> +
> +
> +
> +/* ----------------------- Chunk representations ------------------------
> */
> +
> +/*
> + (The following includes lightly edited explanations by Colin Plumb.)
> +
> + The malloc_chunk declaration below is misleading (but accurate and
> + necessary). It declares a "view" into memory allowing access to
> + necessary fields at known offsets from a given base.
> +
> + Chunks of memory are maintained using a `boundary tag' method as
> + originally described by Knuth. (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 fast. The head fields also hold bits
> + representing whether chunks are free or in use.
> +
> + Here are some pictures to make it clearer. They are "exploded" to
> + show that the state of a chunk can be thought of as extending from
> + the high 31 bits of the head field of its header through the
> + prev_foot and PINUSE_BIT bit of the following chunk header.
> +
> + A chunk that's in use looks like:
> +
> + chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> + | Size of previous chunk (if P = 1) |
> + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|
> + | Size of this chunk 1| +-+
> + mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> + | |
> + +- -+
> + | |
> + +- -+
> + | :
> + +- size - sizeof(size_t) available payload bytes -+
> + : |
> + chunk-> +- -+
> + | |
> + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1|
> + | Size of next chunk (may or may not be in use) | +-+
> + mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> +
> + And if it's free, it looks like this:
> +
> + chunk-> +- -+
> + | User payload (must be in use, or we would have merged!) |
> + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|
> + | Size of this chunk 0| +-+
> + mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> + | Next pointer |
> + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> + | Prev pointer |
> + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> + | :
> + +- size - sizeof(struct chunk) unused bytes -+
> + : |
> + chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> + | Size of this chunk |
> + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0|
> + | Size of next chunk (must be in use, or we would have merged)| +-+
> + mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> + | :
> + +- User payload -+
> + : |
> + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> + |0|
> + +-+
> + Note that since we always merge adjacent free chunks, the chunks
> + adjacent to a free chunk must be in use.
> +
> + Given a pointer to a chunk (which can be derived trivially from the
> + payload pointer) we can, in O(1) time, find out whether the adjacent
> + chunks are free, and if so, unlink them from the lists that they
> + are on and merge them with the current chunk.
> +
> + Chunks always begin on even word boundaries, so the mem portion
> + (which is returned to the user) is also on an even word boundary, and
> + thus at least double-word aligned.
> +
> + The P (PINUSE_BIT) 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. If pinuse is set for
> + any given chunk, then you CANNOT determine the size of the
> + previous chunk, and might even get a memory addressing fault when
> + trying to do so.
> +
> + The C (CINUSE_BIT) bit, stored in the unused second-lowest bit of
> + the chunk size redundantly records whether the current chunk is
> + inuse. This redundancy enables usage checks within free and realloc,
> + and reduces indirection when freeing and consolidating chunks.
> +
> + Each freshly allocated chunk must have both cinuse and pinuse set.
> + That is, each allocated chunk borders either a previously allocated
> + and still in-use chunk, or the base of its memory arena. This is
> + ensured by making all allocations from the the `lowest' part of any
> + found chunk. Further, no free chunk physically borders another one,
> + so each free chunk is known to be preceded and followed by either
> + inuse chunks or the ends of memory.
> +
> + Note that the `foot' of the current chunk is actually represented
> + as the prev_foot of the NEXT chunk. This makes it easier to
> + deal with alignments etc but can be very confusing when trying
> + to extend or adapt this code.
> +
> + The exceptions to all this are
> +
> + 1. The special chunk `top' is the top-most available chunk (i.e.,
> + the one bordering the end of available memory). It is treated
> + specially. Top is never included in any bin, is used only if
> + no other chunk is available, and is released back to the
> + system if it is very large (see M_TRIM_THRESHOLD). In effect,
> + the top chunk is treated as larger (and thus less well
> + fitting) than any other available chunk. The top chunk
> + doesn't update its trailing size field since there is no next
> + contiguous chunk that would have to index off it. However,
> + space is still allocated for it (TOP_FOOT_SIZE) to enable
> + separation or merging when space is extended.
> +
> + 3. Chunks allocated via mmap, which have the lowest-order bit
> + (IS_MMAPPED_BIT) set in their prev_foot fields, and do not set
> + PINUSE_BIT in their head fields. Because they are allocated
> + one-by-one, each must carry its own prev_foot field, which is
> + also used to hold the offset this chunk has within its mmapped
> + region, which is needed to preserve alignment. Each mmapped
> + chunk is trailed by the first two fields of a fake next-chunk
> + for sake of usage checks.
> +
> +*/
> +
> +struct malloc_chunk {
> + size_t prev_foot; /* Size of previous chunk (if free). */
> + size_t head; /* Size and inuse bits. */
> + struct malloc_chunk* fd; /* double links -- used only if free. */
> + struct malloc_chunk* bk;
> +};
> +
> +typedef struct malloc_chunk mchunk;
> +typedef struct malloc_chunk* mchunkptr;
> +typedef struct malloc_chunk* sbinptr; /* The type of bins of chunks */
> +typedef unsigned int bindex_t; /* Described below */
> +typedef unsigned int binmap_t; /* Described below */
> +typedef unsigned int flag_t; /* The type of various bit flag sets
> */
> +
> +
> +/* ------------------- Chunks sizes and alignments -----------------------
> */
> +
> +#define MCHUNK_SIZE (sizeof(mchunk))
> +
> +#if FOOTERS
> +#define CHUNK_OVERHEAD (TWO_SIZE_T_SIZES)
> +#else /* FOOTERS */
> +#define CHUNK_OVERHEAD (SIZE_T_SIZE)
> +#endif /* FOOTERS */
> +
> +/* The smallest size we can malloc is an aligned minimal chunk */
> +#define MIN_CHUNK_SIZE\
> + ((MCHUNK_SIZE + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)
> +
> +/* conversion from malloc headers to user pointers, and back */
> +#define chunk2mem(p) ((void*)((char*)(p) + TWO_SIZE_T_SIZES))
> +#define mem2chunk(mem) ((mchunkptr)((char*)(mem) - TWO_SIZE_T_SIZES))
> +/* chunk associated with aligned address A */
> +#define align_as_chunk(A) (mchunkptr)((A) + align_offset(chunk2mem(A)))
> +
> +/* Bounds on request (not chunk) sizes. */
> +#define MAX_REQUEST ((-MIN_CHUNK_SIZE) << 2)
> +#define MIN_REQUEST (MIN_CHUNK_SIZE - CHUNK_OVERHEAD - SIZE_T_ONE)
> +
> +/* pad request bytes into a usable size */
> +#define pad_request(req) \
> + (((req) + CHUNK_OVERHEAD + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)
> +
> +/* pad request, checking for minimum (but not maximum) */
> +#define request2size(req) \
> + (((req) < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(req))
> +
> +/* ------------------ Operations on head and foot fields -----------------
> */
> +
> +/*
> + The head field of a chunk is or'ed with PINUSE_BIT when previous
> + adjacent chunk in use, and or'ed with CINUSE_BIT if this chunk is in
> + use. If the chunk was obtained with mmap, the prev_foot field has
> + IS_MMAPPED_BIT set, otherwise holding the offset of the base of the
> + mmapped region to the base of the chunk.
> +*/
> +
> +#define PINUSE_BIT (SIZE_T_ONE)
> +#define CINUSE_BIT (SIZE_T_TWO)
> +#define INUSE_BITS (PINUSE_BIT|CINUSE_BIT)
> +
> +/* Head value for fenceposts */
> +#define FENCEPOST_HEAD (INUSE_BITS|SIZE_T_SIZE)
> +
> +/* extraction of fields from head words */
> +#define cinuse(p) ((p)->head & CINUSE_BIT)
> +#define pinuse(p) ((p)->head & PINUSE_BIT)
> +#define chunksize(p) ((p)->head & ~(INUSE_BITS))
> +
> +#define clear_pinuse(p) ((p)->head &= ~PINUSE_BIT)
> +#define clear_cinuse(p) ((p)->head &= ~CINUSE_BIT)
> +
> +/* Treat space at ptr +/- offset as a chunk */
> +#define chunk_plus_offset(p, s) ((mchunkptr)(((char*)(p)) + (s)))
> +#define chunk_minus_offset(p, s) ((mchunkptr)(((char*)(p)) - (s)))
> +
> +/* Ptr to next or previous physical malloc_chunk. */
> +#define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->head &
> ~INUSE_BITS)))
> +#define prev_chunk(p) ((mchunkptr)( ((char*)(p)) - ((p)->prev_foot) ))
> +
> +/* extract next chunk's pinuse bit */
> +#define next_pinuse(p) ((next_chunk(p)->head) & PINUSE_BIT)
> +
> +/* Get/set size at footer */
> +#define get_foot(p, s) (((mchunkptr)((char*)(p) + (s)))->prev_foot)
> +#define set_foot(p, s) (((mchunkptr)((char*)(p) + (s)))->prev_foot = (s))
> +
> +/* Set size, pinuse bit, and foot */
> +#define set_size_and_pinuse_of_free_chunk(p, s)\
> + ((p)->head = (s|PINUSE_BIT), set_foot(p, s))
> +
> +/* Set size, pinuse bit, foot, and clear next pinuse */
> +#define set_free_with_pinuse(p, s, n)\
> + (clear_pinuse(n), set_size_and_pinuse_of_free_chunk(p, s))
> +
> +/* Get the internal overhead associated with chunk p */
> +#define overhead_for(p) CHUNK_OVERHEAD
> +
> +/* Return true if malloced space is not necessarily cleared */
> +#define calloc_must_clear(p) (1)
> +
> +
> +/* ---------------------- Overlaid data structures -----------------------
> */
> +
> +/*
> + When chunks are not in use, they are treated as nodes of either
> + lists or trees.
> +
> + "Small" 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
> |
> +
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> +
> + Larger chunks are kept in a form of bitwise digital trees (aka
> + tries) keyed on chunksizes. Because malloc_tree_chunks are only for
> + free chunks greater than 256 bytes, their size doesn't impose any
> + constraints on user chunk sizes. Each node looks like:
> +
> + chunk->
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> + | Size of previous chunk
> |
> +
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> + `head:' | Size of chunk, in bytes
> |P|
> + mem->
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> + | Forward pointer to next chunk of same size
> |
> +
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> + | Back pointer to previous chunk of same size
> |
> +
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> + | Pointer to left child (child[0])
> |
> +
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> + | Pointer to right child (child[1])
> |
> +
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> + | Pointer to parent
> |
> +
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> + | bin index of this chunk
> |
> +
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> + | Unused space
> .
> + .
> |
> +nextchunk->
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> + `foot:' | Size of chunk, in bytes
> |
> +
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> +
> + Each tree holding treenodes is a tree of unique chunk sizes. Chunks
> + of the same size are arranged in a circularly-linked list, with only
> + the oldest chunk (the next to be used, in our FIFO ordering)
> + actually in the tree. (Tree members are distinguished by a non-null
> + parent pointer.) If a chunk with the same size an an existing node
> + is inserted, it is linked off the existing node using pointers that
> + work in the same way as fd/bk pointers of small chunks.
> +
> + Each tree contains a power of 2 sized range of chunk sizes (the
> + smallest is 0x100 <= x < 0x180), which is is divided in half at each
> + tree level, with the chunks in the smaller half of the range (0x100
> + <= x < 0x140 for the top nose) in the left subtree and the larger
> + half (0x140 <= x < 0x180) in the right subtree. This is, of course,
> + done by inspecting individual bits.
> +
> + Using these rules, each node's left subtree contains all smaller
> + sizes than its right subtree. However, the node at the root of each
> + subtree has no particular ordering relationship to either. (The
> + dividing line between the subtree sizes is based on trie relation.)
> + If we remove the last chunk of a given size from the interior of the
> + tree, we need to replace it with a leaf node. The tree ordering
> + rules permit a node to be replaced by any leaf below it.
> +
> + The smallest chunk in a tree (a common operation in a best-fit
> + allocator) can be found by walking a path to the leftmost leaf in
> + the tree. Unlike a usual binary tree, where we follow left child
> + pointers until we reach a null, here we follow the right child
> + pointer any time the left one is null, until we reach a leaf with
> + both child pointers null. The smallest chunk in the tree will be
> + somewhere along that path.
> +
> + The worst case number of steps to add, find, or remove a node is
> + bounded by the number of bits differentiating chunks within
> + bins. Under current bin calculations, this ranges from 6 up to 21
> + (for 32 bit sizes) or up to 53 (for 64 bit sizes). The typical case
> + is of course much better.
> +*/
> +
> +struct malloc_tree_chunk {
> + /* The first four fields must be compatible with malloc_chunk */
> + size_t prev_foot;
> + size_t head;
> + struct malloc_tree_chunk* fd;
> + struct malloc_tree_chunk* bk;
> +
> + struct malloc_tree_chunk* child[2];
> + struct malloc_tree_chunk* parent;
> + bindex_t index;
> +};
> +
> +typedef struct malloc_tree_chunk tchunk;
> +typedef struct malloc_tree_chunk* tchunkptr;
> +typedef struct malloc_tree_chunk* tbinptr; /* The type of bins of trees */
> +
> +/* A little helper macro for trees */
> +#define leftmost_child(t) ((t)->child[0] != 0? (t)->child[0] :
> (t)->child[1])
> +
> +/* ----------------------------- Segments --------------------------------
> */
> +
> +/*
> + Each malloc space may include non-contiguous segments, held in a
> + list headed by an embedded malloc_segment record representing the
> + top-most space. Segments also include flags holding properties of
> + the space. Large chunks that are directly allocated by mmap are not
> + included in this list. They are instead independently created and
> + destroyed without otherwise keeping track of them.
> +
> + Segment management mainly comes into play for spaces allocated by
> + MMAP. Any call to MMAP might or might not return memory that is
> + adjacent to an existing segment. MORECORE normally contiguously
> + extends the current space, so this space is almost always adjacent,
> + which is simpler and faster to deal with. (This is why MORECORE is
> + used preferentially to MMAP when both are available -- see
> + sys_alloc.) When allocating using MMAP, we don't use any of the
> + hinting mechanisms (inconsistently) supported in various
> + implementations of unix mmap, or distinguish reserving from
> + committing memory. Instead, we just ask for space, and exploit
> + contiguity when we get it. It is probably possible to do
> + better than this on some systems, but no general scheme seems
> + to be significantly better.
> +
> + Management entails a simpler variant of the consolidation scheme
> + used for chunks to reduce fragmentation -- new adjacent memory is
> + normally prepended or appended to an existing segment. However,
> + there are limitations compared to chunk consolidation that mostly
> + reflect the fact that segment processing is relatively infrequent
> + (occurring only when getting memory from system) and that we
> + don't expect to have huge numbers of segments:
> +
> + * Segments are not indexed, so traversal requires linear scans. (It
> + would be possible to index these, but is not worth the extra
> + overhead and complexity for most programs on most platforms.)
> + * New segments are only appended to old ones when holding top-most
> + memory; if they cannot be prepended to others, they are held in
> + different segments.
> +
> + Except for the top-most segment of an mstate, each segment record
> + is kept at the tail of its segment. Segments are added by pushing
> + segment records onto the list headed by &mstate.seg for the
> + containing mstate.
> +
> + Segment flags control allocation/merge/deallocation policies:
> + * If EXTERN_BIT set, then we did not allocate this segment,
> + and so should not try to deallocate or merge with others.
> + (This currently holds only for the initial segment passed
> + into create_mspace_with_base.)
> + * If IS_MMAPPED_BIT set, the segment may be merged with
> + other surrounding mmapped segments and trimmed/de-allocated
> + using munmap.
> + * If neither bit is set, then the segment was obtained using
> + MORECORE so can be merged with surrounding MORECORE'd segments
> + and deallocated/trimmed using MORECORE with negative arguments.
> +*/
> +
> +struct malloc_segment {
> + char* base; /* base address */
> + size_t size; /* allocated size */
> + struct malloc_segment* next; /* ptr to next segment */
> +};
> +
> +typedef struct malloc_segment msegment;
> +typedef struct malloc_segment* msegmentptr;
> +
> +/* ---------------------------- malloc_state -----------------------------
> */
> +
> +/*
> + A malloc_state holds all of the bookkeeping for a space.
> + The main fields are:
> +
> + Top
> + The topmost chunk of the currently active segment. Its size is
> + cached in topsize. The actual size of topmost space is
> + topsize+TOP_FOOT_SIZE, which includes space reserved for adding
> + fenceposts and segment records if necessary when getting more
> + space from the system. The size at which to autotrim top is
> + cached from mparams in trim_check, except that it is disabled if
> + an autotrim fails.
> +
> + Designated victim (dv)
> + This is the preferred chunk for servicing small requests that
> + don't have exact fits. It is normally the chunk split off most
> + recently to service another small request. Its size is cached in
> + dvsize. The link fields of this chunk are not maintained since it
> + is not kept in a bin.
> +
> + SmallBins
> + An array of bin headers for free chunks. These bins hold chunks
> + with sizes less than MIN_LARGE_SIZE bytes. Each bin contains
> + chunks of all the same size, spaced 8 bytes apart. To simplify
> + use in double-linked lists, each bin header acts as a malloc_chunk
> + pointing to the real first node, if it exists (else pointing to
> + itself). This avoids special-casing for headers. But to avoid
> + waste, we allocate only the fd/bk pointers of bins, and then use
> + repositioning tricks to treat these as the fields of a chunk.
> +
> + TreeBins
> + Treebins are pointers to the roots of trees holding a range of
> + sizes. There are 2 equally spaced treebins for each power of two
> + from TREE_SHIFT to TREE_SHIFT+16. The last bin holds anything
> + larger.
> +
> + Bin maps
> + There is one bit map for small bins ("smallmap") and one for
> + treebins ("treemap). Each bin sets its bit when non-empty, and
> + clears the bit when empty. Bit operations are then used to avoid
> + bin-by-bin searching -- nearly all "search" is done without ever
> + looking at bins that won't be selected. The bit maps
> + conservatively use 32 bits per map word, even if on 64bit system.
> + For a good description of some of the bit-based techniques used
> + here, see Henry S. Warren Jr's book "Hacker's Delight" (and
> + supplement at http://hackersdelight.org/). Many of these are
> + intended to reduce the branchiness of paths through malloc etc, as
> + well as to reduce the number of memory locations read or written.
> +
> + Segments
> + A list of segments headed by an embedded malloc_segment record
> + representing the initial space.
> +
> + Address check support
> + The least_addr field is the least address ever obtained from
> + MORECORE or MMAP. Attempted frees and reallocs of any address less
> + than this are trapped (unless INSECURE is defined).
> +
> + Magic tag
> + A cross-check field that should always hold same value as mparams.magic.
> +
> + Flags
> + Bits recording whether to use MMAP, locks, or contiguous MORECORE
> +
> + Statistics
> + Each space keeps track of current and maximum system memory
> + obtained via MORECORE or MMAP.
> +
> + Locking
> + If USE_LOCKS is defined, the "mutex" lock is acquired and released
> + around every public call using this mspace.
> +*/
> +
> +/* Bin types, widths and sizes */
> +#define NSMALLBINS (32U)
> +#define NTREEBINS (32U)
> +#define SMALLBIN_SHIFT (3U)
> +#define SMALLBIN_WIDTH (SIZE_T_ONE << SMALLBIN_SHIFT)
> +#define TREEBIN_SHIFT (8U)
> +#define MIN_LARGE_SIZE (SIZE_T_ONE << TREEBIN_SHIFT)
> +#define MAX_SMALL_SIZE (MIN_LARGE_SIZE - SIZE_T_ONE)
> +#define MAX_SMALL_REQUEST (MAX_SMALL_SIZE - CHUNK_ALIGN_MASK -
> CHUNK_OVERHEAD)
> +
> +struct malloc_state {
> + binmap_t smallmap;
> + binmap_t treemap;
> + size_t dvsize;
> + size_t topsize;
> + char* least_addr;
> + mchunkptr dv;
> + mchunkptr top;
> + size_t magic;
> + mchunkptr smallbins[(NSMALLBINS+1)*2];
> + tbinptr treebins[NTREEBINS];
> + size_t footprint;
> + size_t max_footprint;
> + flag_t mflags;
> + void *user_data;
> +#if USE_LOCKS
> + MLOCK_T mutex; /* locate lock among fields that rarely change */
> +#endif /* USE_LOCKS */
> + msegment seg;
> +};
> +
> +typedef struct malloc_state* mstate;
> +
> +/* ------------- Global malloc_state and malloc_params -------------------
> */
> +
> +/*
> + malloc_params holds global properties, including those that can be
> + dynamically set using mallopt. There is a single instance, mparams,
> + initialized in init_mparams.
> +*/
> +
> +struct malloc_params {
> + size_t magic;
> + size_t page_size;
> + size_t granularity;
> + flag_t default_mflags;
> +};
> +
> +static struct malloc_params mparams;
> +
> +/* The global malloc_state used for all non-"mspace" calls */
> +//static struct malloc_state _gm_;
> +//#define gm (&_gm_)
> +//#define is_global(M) ((M) == &_gm_)
> +#define is_initialized(M) ((M)->top != 0)
> +
> +/* -------------------------- system alloc setup -------------------------
> */
> +
> +/* Operations on mflags */
> +
> +#define use_lock(M) ((M)->mflags & USE_LOCK_BIT)
> +#define enable_lock(M) ((M)->mflags |= USE_LOCK_BIT)
> +#define disable_lock(M) ((M)->mflags &= ~USE_LOCK_BIT)
> +
> +#define set_lock(M,L)\
> + ((M)->mflags = (L)?\
> + ((M)->mflags | USE_LOCK_BIT) :\
> + ((M)->mflags & ~USE_LOCK_BIT))
> +
> +/* page-align a size */
> +#define page_align(S)\
> + (((S) + (mparams.page_size)) & ~(mparams.page_size - SIZE_T_ONE))
> +
> +/* granularity-align a size */
> +#define granularity_align(S)\
> + (((S) + (mparams.granularity)) & ~(mparams.granularity - SIZE_T_ONE))
> +
> +#define is_page_aligned(S)\
> + (((size_t)(S) & (mparams.page_size - SIZE_T_ONE)) == 0)
> +#define is_granularity_aligned(S)\
> + (((size_t)(S) & (mparams.granularity - SIZE_T_ONE)) == 0)
> +
> +/* True if segment S holds address A */
> +#define segment_holds(S, A)\
> + ((char*)(A) >= S->base && (char*)(A) < S->base + S->size)
> +
> +/* Return segment holding given address */
> +static msegmentptr segment_holding(mstate m, char* addr) {
> + msegmentptr sp = &m->seg;
> + for (;;) {
> + if (addr >= sp->base && addr < sp->base + sp->size)
> + return sp;
> + if ((sp = sp->next) == 0)
> + return 0;
> + }
> +}
> +
> +/* Return true if segment contains a segment link */
> +static int has_segment_link(mstate m, msegmentptr ss) {
> + msegmentptr sp = &m->seg;
> + for (;;) {
> + if ((char*)sp >= ss->base && (char*)sp < ss->base + ss->size)
> + return 1;
> + if ((sp = sp->next) == 0)
> + return 0;
> + }
> +}
> +
> +
> +
> +/*
> + TOP_FOOT_SIZE is padding at the end of a segment, including space
> + that may be needed to place segment records and fenceposts when new
> + noncontiguous segments are added.
> +*/
> +#define TOP_FOOT_SIZE\
> + (align_offset(chunk2mem(0))+pad_request(sizeof(struct
> malloc_segment))+MIN_CHUNK_SIZE)
> +
> +
> +/* ------------------------------- Hooks --------------------------------
> */
> +
> +/*
> + PREACTION should be defined to return 0 on success, and nonzero on
> + failure. If you are not using locking, you can redefine these to do
> + anything you like.
> +*/
> +
> +#if USE_LOCKS
> +
> +/* Ensure locks are initialized */
> +#define GLOBALLY_INITIALIZE() (mparams.page_size == 0 && init_mparams())
> +
> +#define PREACTION(M) ((GLOBALLY_INITIALIZE() || use_lock(M))?
> ACQUIRE_LOCK(&(M)->mutex) : 0)
> +#define POSTACTION(M) { if (use_lock(M)) RELEASE_LOCK(&(M)->mutex); }
> +#else /* USE_LOCKS */
> +
> +#ifndef PREACTION
> +#define PREACTION(M) (0)
> +#endif /* PREACTION */
> +
> +#ifndef POSTACTION
> +#define POSTACTION(M)
> +#endif /* POSTACTION */
> +
> +#endif /* USE_LOCKS */
> +
> +/*
> + CORRUPTION_ERROR_ACTION is triggered upon detected bad addresses.
> + USAGE_ERROR_ACTION is triggered on detected bad frees and
> + reallocs. The argument p is an address that might have triggered the
> + fault. It is ignored by the two predefined actions, but might be
> + useful in custom actions that try to help diagnose errors.
> +*/
> +
> +#if PROCEED_ON_ERROR
> +
> +/* A count of the number of corruption errors causing resets */
> +int malloc_corruption_error_count;
> +
> +/* default corruption action */
> +static void reset_on_error(mstate m);
> +
> +#define CORRUPTION_ERROR_ACTION(m) reset_on_error(m)
> +#define USAGE_ERROR_ACTION(m, p)
> +
> +#else /* PROCEED_ON_ERROR */
> +
> +#ifndef CORRUPTION_ERROR_ACTION
> +#define CORRUPTION_ERROR_ACTION(m) ABORT(m->user_data)
> +#endif /* CORRUPTION_ERROR_ACTION */
> +
> +#ifndef USAGE_ERROR_ACTION
> +#define USAGE_ERROR_ACTION(m,p) ABORT(m->user_data)
> +#endif /* USAGE_ERROR_ACTION */
> +
> +#endif /* PROCEED_ON_ERROR */
> +
> +/* -------------------------- Debugging setup ----------------------------
> */
> +
> +#if ! DEBUG
> +
> +#define check_free_chunk(M,P)
> +#define check_inuse_chunk(M,P)
> +#define check_malloced_chunk(M,P,N)
> +#define check_malloc_state(M)
> +#define check_top_chunk(M,P)
> +
> +#else /* DEBUG */
> +#define check_free_chunk(M,P) do_check_free_chunk(M,P)
> +#define check_inuse_chunk(M,P) do_check_inuse_chunk(M,P)
> +#define check_top_chunk(M,P) do_check_top_chunk(M,P)
> +#define check_malloced_chunk(M,P,N) do_check_malloced_chunk(M,P,N)
> +#define check_malloc_state(M) do_check_malloc_state(M)
> +
> +static void do_check_any_chunk(mstate m, mchunkptr p);
> +static void do_check_top_chunk(mstate m, mchunkptr p);
> +static void do_check_inuse_chunk(mstate m, mchunkptr p);
> +static void do_check_free_chunk(mstate m, mchunkptr p);
> +static void do_check_malloced_chunk(mstate m, void* mem, size_t s);
> +static void do_check_tree(mstate m, tchunkptr t);
> +static void do_check_treebin(mstate m, bindex_t i);
> +static void do_check_smallbin(mstate m, bindex_t i);
> +static void do_check_malloc_state(mstate m);
> +static int bin_find(mstate m, mchunkptr x);
> +static size_t traverse_and_check(mstate m);
> +#endif /* DEBUG */
> +
> +/* ---------------------------- Indexing Bins ----------------------------
> */
> +
> +#define is_small(s) (((s) >> SMALLBIN_SHIFT) < NSMALLBINS)
> +#define small_index(s) ((s) >> SMALLBIN_SHIFT)
> +#define small_index2size(i) ((i) << SMALLBIN_SHIFT)
> +#define MIN_SMALL_INDEX (small_index(MIN_CHUNK_SIZE))
> +
> +/* addressing by index. See above about smallbin repositioning */
> +#define smallbin_at(M, i) ((sbinptr)((char*)&((M)->smallbins[(i)<<1])))
> +#define treebin_at(M,i) (&((M)->treebins[i]))
> +
> +/* assign tree index for size S to variable I */
> +#if defined(__GNUC__) && defined(i386)
> +#define compute_tree_index(S, I)\
> +{\
> + size_t X = S >> TREEBIN_SHIFT;\
> + if (X == 0)\
> + I = 0;\
> + else if (X > 0xFFFF)\
> + I = NTREEBINS-1;\
> + else {\
> + unsigned int K;\
> + __asm__("bsrl %1,%0\n\t" : "=r" (K) : "rm" (X));\
> + I = (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\
> + }\
> +}
> +#else /* GNUC */
> +#define compute_tree_index(S, I)\
> +{\
> + size_t X = S >> TREEBIN_SHIFT;\
> + if (X == 0)\
> + I = 0;\
> + else if (X > 0xFFFF)\
> + I = NTREEBINS-1;\
> + else {\
> + unsigned int Y = (unsigned int)X;\
> + unsigned int N = ((Y - 0x100) >> 16) & 8;\
> + unsigned int K = (((Y <<= N) - 0x1000) >> 16) & 4;\
> + N += K;\
> + N += K = (((Y <<= K) - 0x4000) >> 16) & 2;\
> + K = 14 - N + ((Y <<= K) >> 15);\
> + I = (K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1));\
> + }\
> +}
> +#endif /* GNUC */
> +
> +/* Bit representing maximum resolved size in a treebin at i */
> +#define bit_for_tree_index(i) \
> + (i == NTREEBINS-1)? (SIZE_T_BITSIZE-1) : (((i) >> 1) + TREEBIN_SHIFT - 2)
> +
> +/* Shift placing maximum resolved bit in a treebin at i as sign bit */
> +#define leftshift_for_tree_index(i) \
> + ((i == NTREEBINS-1)? 0 : \
> + ((SIZE_T_BITSIZE-SIZE_T_ONE) - (((i) >> 1) + TREEBIN_SHIFT - 2)))
> +
> +/* The size of the smallest chunk held in bin with index i */
> +#define minsize_for_tree_index(i) \
> + ((SIZE_T_ONE << (((i) >> 1) + TREEBIN_SHIFT)) | \
> + (((size_t)((i) & SIZE_T_ONE)) << (((i) >> 1) + TREEBIN_SHIFT - 1)))
> +
> +/* ------------------------ Operations on bin maps -----------------------
> */
> +
> +/* bit corresponding to given index */
> +#define idx2bit(i) ((binmap_t)(1) << (i))
> +
> +/* Mark/Clear bits with given index */
> +#define mark_smallmap(M,i) ((M)->smallmap |= idx2bit(i))
> +#define clear_smallmap(M,i) ((M)->smallmap &= ~idx2bit(i))
> +#define smallmap_is_marked(M,i) ((M)->smallmap & idx2bit(i))
> +
> +#define mark_treemap(M,i) ((M)->treemap |= idx2bit(i))
> +#define clear_treemap(M,i) ((M)->treemap &= ~idx2bit(i))
> +#define treemap_is_marked(M,i) ((M)->treemap & idx2bit(i))
> +
> +/* index corresponding to given bit */
> +
> +#if defined(__GNUC__) && defined(i386)
> +#define compute_bit2idx(X, I)\
> +{\
> + unsigned int J;\
> + __asm__("bsfl %1,%0\n\t" : "=r" (J) : "rm" (X));\
> + I = (bindex_t)J;\
> +}
> +
> +#else /* GNUC */
> +#if USE_BUILTIN_FFS
> +#define compute_bit2idx(X, I) I = ffs(X)-1
> +
> +#else /* USE_BUILTIN_FFS */
> +#define compute_bit2idx(X, I)\
> +{\
> + unsigned int Y = X - 1;\
> + unsigned int K = Y >> (16-4) & 16;\
> + unsigned int N = K; Y >>= K;\
> + N += K = Y >> (8-3) & 8; Y >>= K;\
> + N += K = Y >> (4-2) & 4; Y >>= K;\
> + N += K = Y >> (2-1) & 2; Y >>= K;\
> + N += K = Y >> (1-0) & 1; Y >>= K;\
> + I = (bindex_t)(N + Y);\
> +}
> +#endif /* USE_BUILTIN_FFS */
> +#endif /* GNUC */
> +
> +/* isolate the least set bit of a bitmap */
> +#define least_bit(x) ((x) & -(x))
> +
> +/* mask with all bits to left of least bit of x on */
> +#define left_bits(x) ((x<<1) | -(x<<1))
> +
> +/* mask with all bits to left of or equal to least bit of x on */
> +#define same_or_left_bits(x) ((x) | -(x))
> +
> +
> +/* ----------------------- Runtime Check Support -------------------------
> */
> +
> +/*
> + For security, the main invariant is that malloc/free/etc never
> + writes to a static address other than malloc_state, unless static
> + malloc_state itself has been corrupted, which cannot occur via
> + malloc (because of these checks). In essence this means that we
> + believe all pointers, sizes, maps etc held in malloc_state, but
> + check all of those linked or offsetted from other embedded data
> + structures. These checks are interspersed with main code in a way
> + that tends to minimize their run-time cost.
> +
> + When FOOTERS is defined, in addition to range checking, we also
> + verify footer fields of inuse chunks, which can be used guarantee
> + that the mstate controlling malloc/free is intact. This is a
> + streamlined version of the approach described by William Robertson
> + et al in "Run-time Detection of Heap-based Overflows" LISA'03
> + http://www.usenix.org/events/lisa03/tech/robertson.html The footer
> + of an inuse chunk holds the xor of its mstate and a random seed,
> + that is checked upon calls to free() and realloc(). This is
> + (probablistically) unguessable from outside the program, but can be
> + computed by any code successfully malloc'ing any chunk, so does not
> + itself provide protection against code that has already broken
> + security through some other means. Unlike Robertson et al, we
> + always dynamically check addresses of all offset chunks (previous,
> + next, etc). This turns out to be cheaper than relying on hashes.
> +*/
> +
> +#if !INSECURE
> +/* Check if address a is at least as high as any from MORECORE or MMAP */
> +#define ok_address(M, a) ((char*)(a) >= (M)->least_addr)
> +/* Check if address of next chunk n is higher than base chunk p */
> +#define ok_next(p, n) ((char*)(p) < (char*)(n))
> +/* Check if p has its cinuse bit on */
> +#define ok_cinuse(p) cinuse(p)
> +/* Check if p has its pinuse bit on */
> +#define ok_pinuse(p) pinuse(p)
> +
> +#else /* !INSECURE */
> +#define ok_address(M, a) (1)
> +#define ok_next(b, n) (1)
> +#define ok_cinuse(p) (1)
> +#define ok_pinuse(p) (1)
> +#endif /* !INSECURE */
> +
> +#if (FOOTERS && !INSECURE)
> +/* Check if (alleged) mstate m has expected magic field */
> +#define ok_magic(M) ((M)->magic == mparams.magic)
> +#else /* (FOOTERS && !INSECURE) */
> +#define ok_magic(M) (1)
> +#endif /* (FOOTERS && !INSECURE) */
> +
> +
> +/* In gcc, use __builtin_expect to minimize impact of checks */
> +#if !INSECURE
> +#if defined(__GNUC__) && __GNUC__ >= 3
> +#define RTCHECK(e) __builtin_expect(e, 1)
> +#else /* GNUC */
> +#define RTCHECK(e) (e)
> +#endif /* GNUC */
> +#else /* !INSECURE */
> +#define RTCHECK(e) (1)
> +#endif /* !INSECURE */
> +
> +/* macros to set up inuse chunks with or without footers */
> +
> +#if !FOOTERS
> +
> +#define mark_inuse_foot(M,p,s)
> +
> +/* Set cinuse bit and pinuse bit of next chunk */
> +#define set_inuse(M,p,s)\
> + ((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\
> + ((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT)
> +
> +/* Set cinuse and pinuse of this chunk and pinuse of next chunk */
> +#define set_inuse_and_pinuse(M,p,s)\
> + ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
> + ((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT)
> +
> +/* Set size, cinuse and pinuse bit of this chunk */
> +#define set_size_and_pinuse_of_inuse_chunk(M, p, s)\
> + ((p)->head = (s|PINUSE_BIT|CINUSE_BIT))
> +
> +#else /* FOOTERS */
> +
> +/* Set foot of inuse chunk to be xor of mstate and seed */
> +#define mark_inuse_foot(M,p,s)\
> + (((mchunkptr)((char*)(p) + (s)))->prev_foot = ((size_t)(M) ^
> mparams.magic))
> +
> +#define get_mstate_for(p)\
> + ((mstate)(((mchunkptr)((char*)(p) +\
> + (chunksize(p))))->prev_foot ^ mparams.magic))
> +
> +#define set_inuse(M,p,s)\
> + ((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\
> + (((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT), \
> + mark_inuse_foot(M,p,s))
> +
> +#define set_inuse_and_pinuse(M,p,s)\
> + ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
> + (((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT),\
> + mark_inuse_foot(M,p,s))
> +
> +#define set_size_and_pinuse_of_inuse_chunk(M, p, s)\
> + ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
> + mark_inuse_foot(M, p, s))
> +
> +#endif /* !FOOTERS */
> +
> +/* ---------------------------- setting mparams --------------------------
> */
> +
> +/* Initialize mparams */
> +static int init_mparams(void) {
> + if (mparams.page_size == 0) {
> + size_t s;
> +
> + mparams.default_mflags = USE_LOCK_BIT;
> +
> +#if (FOOTERS && !INSECURE)
> + {
> +#if USE_DEV_RANDOM
> + int fd;
> + unsigned char buf[sizeof(size_t)];
> + /* Try to use /dev/urandom, else fall back on using time */
> + if ((fd = open("/dev/urandom", O_RDONLY)) >= 0 &&
> + read(fd, buf, sizeof(buf)) == sizeof(buf)) {
> + s = *((size_t *) buf);
> + close(fd);
> + }
> + else
> +#endif /* USE_DEV_RANDOM */
> + s = (size_t)(time(0) ^ (size_t)0x55555555U);
> +
> + s |= (size_t)8U; /* ensure nonzero */
> + s &= ~(size_t)7U; /* improve chances of fault for bad values */
> +
> + }
> +#else /* (FOOTERS && !INSECURE) */
> + s = (size_t)0x58585858U;
> +#endif /* (FOOTERS && !INSECURE) */
> + ACQUIRE_MAGIC_INIT_LOCK();
> + if (mparams.magic == 0) {
> + mparams.magic = s;
> + /* Set up lock for main malloc area */
> + //INITIAL_LOCK(&gm->mutex);
> + //gm->mflags = mparams.default_mflags;
> + }
> + RELEASE_MAGIC_INIT_LOCK();
> +
> +
> + mparams.page_size = malloc_getpagesize;
> + mparams.granularity = ((DEFAULT_GRANULARITY != 0)?
> + DEFAULT_GRANULARITY : mparams.page_size);
> +
> + /* Sanity-check configuration:
> + size_t must be unsigned and as wide as pointer type.
> + ints must be at least 4 bytes.
> + alignment must be at least 8.
> + Alignment, min chunk size, and page size must all be powers of 2.
> + */
> + if ((sizeof(size_t) != sizeof(char*)) ||
> + (MAX_SIZE_T < MIN_CHUNK_SIZE) ||
> + (sizeof(int) < 4) ||
> + (MALLOC_ALIGNMENT < (size_t)8U) ||
> + ((MALLOC_ALIGNMENT & (MALLOC_ALIGNMENT-SIZE_T_ONE)) != 0) ||
> + ((MCHUNK_SIZE & (MCHUNK_SIZE-SIZE_T_ONE)) != 0) ||
> + ((mparams.granularity & (mparams.granularity-SIZE_T_ONE)) != 0) ||
> + ((mparams.page_size & (mparams.page_size-SIZE_T_ONE)) != 0))
> + ABORT(NULL);
> + }
> + return 0;
> +}
> +
> +/* support for mallopt */
> +static int change_mparam(int param_number, int value) {
> + size_t val = (size_t)value;
> + init_mparams();
> + switch(param_number) {
> + case M_GRANULARITY:
> + if (val >= mparams.page_size && ((val & (val-1)) == 0)) {
> + mparams.granularity = val;
> + return 1;
> + }
> + else
> + return 0;
> + default:
> + return 0;
> + }
> +}
> +
> +#if DEBUG
> +/* ------------------------- Debugging Support ---------------------------
> */
> +
> +/* Check properties of any chunk, whether free, inuse, mmapped etc */
> +static void do_check_any_chunk(mstate m, mchunkptr p) {
> + assert(m->user_data, (is_aligned(chunk2mem(p))) || (p->head ==
> FENCEPOST_HEAD));
> + assert(m->user_data, ok_address(m, p));
> +}
> +
> +/* Check properties of top chunk */
> +static void do_check_top_chunk(mstate m, mchunkptr p) {
> + msegmentptr sp = segment_holding(m, (char*)p);
> + size_t sz = chunksize(p);
> + assert(m->user_data, sp != 0);
> + assert(m->user_data, (is_aligned(chunk2mem(p))) || (p->head ==
> FENCEPOST_HEAD));
> + assert(m->user_data, ok_address(m, p));
> + assert(m->user_data, sz == m->topsize);
> + assert(m->user_data, sz > 0);
> + assert(m->user_data, sz == ((sp->base + sp->size) - (char*)p) -
> TOP_FOOT_SIZE);
> + assert(m->user_data, pinuse(p));
> + assert(m->user_data, !next_pinuse(p));
> +}
> +
> +/* Check properties of inuse chunks */
> +static void do_check_inuse_chunk(mstate m, mchunkptr p) {
> + do_check_any_chunk(m, p);
> + assert(m->user_data, cinuse(p));
> + assert(m->user_data, next_pinuse(p));
> + /* If not pinuse, previous chunk has OK offset */
> + assert(m->user_data, pinuse(p) || next_chunk(prev_chunk(p)) == p);
> +}
> +
> +/* Check properties of free chunks */
> +static void do_check_free_chunk(mstate m, mchunkptr p) {
> + size_t sz = p->head & ~(PINUSE_BIT|CINUSE_BIT);
> + mchunkptr next = chunk_plus_offset(p, sz);
> + do_check_any_chunk(m, p);
> + assert(m->user_data, !cinuse(p));
> + assert(m->user_data, !next_pinuse(p));
> + if (p != m->dv && p != m->top) {
> + if (sz >= MIN_CHUNK_SIZE) {
> + assert(m->user_data, (sz & CHUNK_ALIGN_MASK) == 0);
> + assert(m->user_data, is_aligned(chunk2mem(p)));
> + assert(m->user_data, next->prev_foot == sz);
> + assert(m->user_data, pinuse(p));
> + assert(m->user_data, next == m->top || cinuse(next));
> + assert(m->user_data, p->fd->bk == p);
> + assert(m->user_data, p->bk->fd == p);
> + }
> + else /* markers are always of size SIZE_T_SIZE */
> + assert(m->user_data, sz == SIZE_T_SIZE);
> + }
> +}
> +
> +/* Check properties of malloced chunks at the point they are malloced */
> +static void do_check_malloced_chunk(mstate m, void* mem, size_t s) {
> + if (mem != 0) {
> + mchunkptr p = mem2chunk(mem);
> + size_t sz = p->head & ~(PINUSE_BIT|CINUSE_BIT);
> + do_check_inuse_chunk(m, p);
> + assert(m->user_data, (sz & CHUNK_ALIGN_MASK) == 0);
> + assert(m->user_data, sz >= MIN_CHUNK_SIZE);
> + assert(m->user_data, sz >= s);
> + /* size is less than MIN_CHUNK_SIZE more than request */
> + assert(m->user_data, sz < (s + MIN_CHUNK_SIZE));
> + }
> +}
> +
> +/* Check a tree and its subtrees. */
> +static void do_check_tree(mstate m, tchunkptr t) {
> + tchunkptr head = 0;
> + tchunkptr u = t;
> + bindex_t tindex = t->index;
> + size_t tsize = chunksize(t);
> + bindex_t idx;
> + compute_tree_index(tsize, idx);
> + assert(m->user_data, tindex == idx);
> + assert(m->user_data, tsize >= MIN_LARGE_SIZE);
> + assert(m->user_data, tsize >= minsize_for_tree_index(idx));
> + assert(m->user_data, (idx == NTREEBINS-1) || (tsize <
> minsize_for_tree_index((idx+1))));
> +
> + do { /* traverse through chain of same-sized nodes */
> + do_check_any_chunk(m, ((mchunkptr)u));
> + assert(m->user_data, u->index == tindex);
> + assert(m->user_data, chunksize(u) == tsize);
> + assert(m->user_data, !cinuse(u));
> + assert(m->user_data, !next_pinuse(u));
> + assert(m->user_data, u->fd->bk == u);
> + assert(m->user_data, u->bk->fd == u);
> + if (u->parent == 0) {
> + assert(m->user_data, u->child[0] == 0);
> + assert(m->user_data, u->child[1] == 0);
> + }
> + else {
> + assert(m->user_data, head == 0); /* only one node on chain has parent
> */
> + head = u;
> + assert(m->user_data, u->parent != u);
> + assert(m->user_data, u->parent->child[0] == u ||
> + u->parent->child[1] == u ||
> + *((tbinptr*)(u->parent)) == u);
> + if (u->child[0] != 0) {
> + assert(m->user_data, u->child[0]->parent == u);
> + assert(m->user_data, u->child[0] != u);
> + do_check_tree(m, u->child[0]);
> + }
> + if (u->child[1] != 0) {
> + assert(m->user_data, u->child[1]->parent == u);
> + assert(m->user_data, u->child[1] != u);
> + do_check_tree(m, u->child[1]);
> + }
> + if (u->child[0] != 0 && u->child[1] != 0) {
> + assert(m->user_data, chunksize(u->child[0]) <
> chunksize(u->child[1]));
> + }
> + }
> + u = u->fd;
> + } while (u != t);
> + assert(m->user_data, head != 0);
> +}
> +
> +/* Check all the chunks in a treebin. */
> +static void do_check_treebin(mstate m, bindex_t i) {
> + tbinptr* tb = treebin_at(m, i);
> + tchunkptr t = *tb;
> + int empty = (m->treemap & (1U << i)) == 0;
> + if (t == 0)
> + assert(m->user_data, empty);
> + if (!empty)
> + do_check_tree(m, t);
> +}
> +
> +/* Check all the chunks in a smallbin. */
> +static void do_check_smallbin(mstate m, bindex_t i) {
> + sbinptr b = smallbin_at(m, i);
> + mchunkptr p = b->bk;
> + unsigned int empty = (m->smallmap & (1U << i)) == 0;
> + if (p == b)
> + assert(m->user_data, empty);
> + if (!empty) {
> + for (; p != b; p = p->bk) {
> + size_t size = chunksize(p);
> + mchunkptr q;
> + /* each chunk claims to be free */
> + do_check_free_chunk(m, p);
> + /* chunk belongs in bin */
> + assert(m->user_data, small_index(size) == i);
> + assert(m->user_data, p->bk == b || chunksize(p->bk) == chunksize(p));
> + /* chunk is followed by an inuse chunk */
> + q = next_chunk(p);
> + if (q->head != FENCEPOST_HEAD)
> + do_check_inuse_chunk(m, q);
> + }
> + }
> +}
> +
> +/* Find x in a bin. Used in other check functions. */
> +static int bin_find(mstate m, mchunkptr x) {
> + size_t size = chunksize(x);
> + if (is_small(size)) {
> + bindex_t sidx = small_index(size);
> + sbinptr b = smallbin_at(m, sidx);
> + if (smallmap_is_marked(m, sidx)) {
> + mchunkptr p = b;
> + do {
> + if (p == x)
> + return 1;
> + } while ((p = p->fd) != b);
> + }
> + }
> + else {
> + bindex_t tidx;
> + compute_tree_index(size, tidx);
> + if (treemap_is_marked(m, tidx)) {
> + tchunkptr t = *treebin_at(m, tidx);
> + size_t sizebits = size << leftshift_for_tree_index(tidx);
> + while (t != 0 && chunksize(t) != size) {
> + t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1];
> + sizebits <<= 1;
> + }
> + if (t != 0) {
> + tchunkptr u = t;
> + do {
> + if (u == (tchunkptr)x)
> + return 1;
> + } while ((u = u->fd) != t);
> + }
> + }
> + }
> + return 0;
> +}
> +
> +/* Traverse each chunk and check it; return total */
> +static size_t traverse_and_check(mstate m) {
> + size_t sum = 0;
> + if (is_initialized(m)) {
> + msegmentptr s = &m->seg;
> + sum += m->topsize + TOP_FOOT_SIZE;
> + while (s != 0) {
> + mchunkptr q = align_as_chunk(s->base);
> + mchunkptr lastq = 0;
> + assert(m->user_data, pinuse(q));
> + while (segment_holds(s, q) &&
> + q != m->top && q->head != FENCEPOST_HEAD) {
> + sum += chunksize(q);
> + if (cinuse(q)) {
> + assert(m->user_data, !bin_find(m, q));
> + do_check_inuse_chunk(m, q);
> + }
> + else {
> + assert(m->user_data, q == m->dv || bin_find(m, q));
> + assert(m->user_data, lastq == 0 || cinuse(lastq)); /* Not 2
> consecutive free */
> + do_check_free_chunk(m, q);
> + }
> + lastq = q;
> + q = next_chunk(q);
> + }
> + s = s->next;
> + }
> + }
> + return sum;
> +}
> +
> +/* Check all properties of malloc_state. */
> +static void do_check_malloc_state(mstate m) {
> + bindex_t i;
> + size_t total;
> + /* check bins */
> + for (i = 0; i < NSMALLBINS; ++i)
> + do_check_smallbin(m, i);
> + for (i = 0; i < NTREEBINS; ++i)
> + do_check_treebin(m, i);
> +
> + if (m->dvsize != 0) { /* check dv chunk */
> + do_check_any_chunk(m, m->dv);
> + assert(m->user_data, m->dvsize == chunksize(m->dv));
> + assert(m->user_data, m->dvsize >= MIN_CHUNK_SIZE);
> + assert(m->user_data, bin_find(m, m->dv) == 0);
> + }
> +
> + if (m->top != 0) { /* check top chunk */
> + do_check_top_chunk(m, m->top);
> + assert(m->user_data, m->topsize == chunksize(m->top));
> + assert(m->user_data, m->topsize > 0);
> + assert(m->user_data, bin_find(m, m->top) == 0);
> + }
> +
> + total = traverse_and_check(m);
> + assert(m->user_data, total <= m->footprint);
> + assert(m->user_data, m->footprint <= m->max_footprint);
> +}
> +#endif /* DEBUG */
> +
> +/* ----------------------------- statistics ------------------------------
> */
> +
> +#if !NO_MALLINFO
> +static struct mallinfo internal_mallinfo(mstate m) {
> + struct mallinfo nm = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
> + if (!PREACTION(m)) {
> + check_malloc_state(m);
> + if (is_initialized(m)) {
> + size_t nfree = SIZE_T_ONE; /* top always free */
> + size_t mfree = m->topsize + TOP_FOOT_SIZE;
> + size_t sum = mfree;
> + msegmentptr s = &m->seg;
> + while (s != 0) {
> + mchunkptr q = align_as_chunk(s->base);
> + while (segment_holds(s, q) &&
> + q != m->top && q->head != FENCEPOST_HEAD) {
> + size_t sz = chunksize(q);
> + sum += sz;
> + if (!cinuse(q)) {
> + mfree += sz;
> + ++nfree;
> + }
> + q = next_chunk(q);
> + }
> + s = s->next;
> + }
> +
> + nm.arena = sum;
> + nm.ordblks = nfree;
> + nm.hblkhd = m->footprint - sum;
> + nm.usmblks = m->max_footprint;
> + nm.uordblks = m->footprint - mfree;
> + nm.fordblks = mfree;
> + nm.keepcost = m->topsize;
> + }
> +
> + POSTACTION(m);
> + }
> + return nm;
> +}
> +#endif /* !NO_MALLINFO */
> +
> +static void internal_malloc_stats(mstate m) {
> + if (!PREACTION(m)) {
> + size_t maxfp = 0;
> + size_t fp = 0;
> + size_t used = 0;
> + check_malloc_state(m);
> + if (is_initialized(m)) {
> + msegmentptr s = &m->seg;
> + maxfp = m->max_footprint;
> + fp = m->footprint;
> + used = fp - (m->topsize + TOP_FOOT_SIZE);
> +
> + while (s != 0) {
> + mchunkptr q = align_as_chunk(s->base);
> + while (segment_holds(s, q) &&
> + q != m->top && q->head != FENCEPOST_HEAD) {
> + if (!cinuse(q))
> + used -= chunksize(q);
> + q = next_chunk(q);
> + }
> + s = s->next;
> + }
> + }
> +
> + PRINT((m->user_data, "max system bytes = %10lu\n", (unsigned
> long)(maxfp)));
> + PRINT((m->user_data, "system bytes = %10lu\n", (unsigned
> long)(fp)));
> + PRINT((m->user_data, "in use bytes = %10lu\n", (unsigned
> long)(used)));
> +
> + POSTACTION(m);
> + }
> +}
> +
> +/* ----------------------- Operations on smallbins -----------------------
> */
> +
> +/*
> + Various forms of linking and unlinking are defined as macros. Even
> + the ones for trees, which are very long but have very short typical
> + paths. This is ugly but reduces reliance on inlining support of
> + compilers.
> +*/
> +
> +/* Link a free chunk into a smallbin */
> +#define insert_small_chunk(M, P, S) {\
> + bindex_t I = small_index(S);\
> + mchunkptr B = smallbin_at(M, I);\
> + mchunkptr F = B;\
> + assert((M)->user_data, S >= MIN_CHUNK_SIZE);\
> + if (!smallmap_is_marked(M, I))\
> + mark_smallmap(M, I);\
> + else if (RTCHECK(ok_address(M, B->fd)))\
> + F = B->fd;\
> + else {\
> + CORRUPTION_ERROR_ACTION(M);\
> + }\
> + B->fd = P;\
> + F->bk = P;\
> + P->fd = F;\
> + P->bk = B;\
> +}
> +
> +/* Unlink a chunk from a smallbin */
> +#define unlink_small_chunk(M, P, S) {\
> + mchunkptr F = P->fd;\
> + mchunkptr B = P->bk;\
> + bindex_t I = small_index(S);\
> + assert((M)->user_data, P != B);\
> + assert((M)->user_data, P != F);\
> + assert((M)->user_data, chunksize(P) == small_index2size(I));\
> + if (F == B)\
> + clear_smallmap(M, I);\
> + else if (RTCHECK((F == smallbin_at(M,I) || ok_address(M, F)) &&\
> + (B == smallbin_at(M,I) || ok_address(M, B)))) {\
> + F->bk = B;\
> + B->fd = F;\
> + }\
> + else {\
> + CORRUPTION_ERROR_ACTION(M);\
> + }\
> +}
> +
> +/* Unlink the first chunk from a smallbin */
> +#define unlink_first_small_chunk(M, B, P, I) {\
> + mchunkptr F = P->fd;\
> + assert((M)->user_data, P != B);\
> + assert((M)->user_data, P != F);\
> + assert((M)->user_data, chunksize(P) == small_index2size(I));\
> + if (B == F)\
> + clear_smallmap(M, I);\
> + else if (RTCHECK(ok_address(M, F))) {\
> + B->fd = F;\
> + F->bk = B;\
> + }\
> + else {\
> + CORRUPTION_ERROR_ACTION(M);\
> + }\
> +}
> +
> +/* Replace dv node, binning the old one */
> +/* Used only when dvsize known to be small */
> +#define replace_dv(M, P, S) {\
> + size_t DVS = M->dvsize;\
> + if (DVS != 0) {\
> + mchunkptr DV = M->dv;\
> + assert((M)->user_data, is_small(DVS));\
> + insert_small_chunk(M, DV, DVS);\
> + }\
> + M->dvsize = S;\
> + M->dv = P;\
> +}
> +
> +
> +/* ------------------------- Operations on trees -------------------------
> */
> +
> +/* Insert chunk into tree */
> +#define insert_large_chunk(M, X, S) {\
> + tbinptr* H;\
> + bindex_t I;\
> + compute_tree_index(S, I);\
> + H = treebin_at(M, I);\
> + X->index = I;\
> + X->child[0] = X->child[1] = 0;\
> + if (!treemap_is_marked(M, I)) {\
> + mark_treemap(M, I);\
> + *H = X;\
> + X->parent = (tchunkptr)H;\
> + X->fd = X->bk = X;\
> + }\
> + else {\
> + tchunkptr T = *H;\
> + size_t K = S << leftshift_for_tree_index(I);\
> + for (;;) {\
> + if (chunksize(T) != S) {\
> + tchunkptr* C = &(T->child[(K >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1]);\
> + K <<= 1;\
> + if (*C != 0)\
> + T = *C;\
> + else if (RTCHECK(ok_address(M, C))) {\
> + *C = X;\
> + X->parent = T;\
> + X->fd = X->bk = X;\
> + break;\
> + }\
> + else {\
> + CORRUPTION_ERROR_ACTION(M);\
> + break;\
> + }\
> + }\
> + else {\
> + tchunkptr F = T->fd;\
> + if (RTCHECK(ok_address(M, T) && ok_address(M, F))) {\
> + T->fd = F->bk = X;\
> + X->fd = F;\
> + X->bk = T;\
> + X->parent = 0;\
> + break;\
> + }\
> + else {\
> + CORRUPTION_ERROR_ACTION(M);\
> + break;\
> + }\
> + }\
> + }\
> + }\
> +}
> +
> +/*
> + Unlink steps:
> +
> + 1. If x is a chained node, unlink it from its same-sized fd/bk links
> + and choose its bk node as its replacement.
> + 2. If x was the last node of its size, but not a leaf node, it must
> + be replaced with a leaf node (not merely one with an open left or
> + right), to make sure that lefts and rights of descendents
> + correspond properly to bit masks. We use the rightmost descendent
> + of x. We could use any other leaf, but this is easy to locate and
> + tends to counteract removal of leftmosts elsewhere, and so keeps
> + paths shorter than minimally guaranteed. This doesn't loop much
> + because on average a node in a tree is near the bottom.
> + 3. If x is the base of a chain (i.e., has parent links) relink
> + x's parent and children to x's replacement (or null if none).
> +*/
> +
> +#define unlink_large_chunk(M, X) {\
> + tchunkptr XP = X->parent;\
> + tchunkptr R;\
> + if (X->bk != X) {\
> + tchunkptr F = X->fd;\
> + R = X->bk;\
> + if (RTCHECK(ok_address(M, F))) {\
> + F->bk = R;\
> + R->fd = F;\
> + }\
> + else {\
> + CORRUPTION_ERROR_ACTION(M);\
> + }\
> + }\
> + else {\
> + tchunkptr* RP;\
> + if (((R = *(RP = &(X->child[1]))) != 0) ||\
> + ((R = *(RP = &(X->child[0]))) != 0)) {\
> + tchunkptr* CP;\
> + while ((*(CP = &(R->child[1])) != 0) ||\
> + (*(CP = &(R->child[0])) != 0)) {\
> + R = *(RP = CP);\
> + }\
> + if (RTCHECK(ok_address(M, RP)))\
> + *RP = 0;\
> + else {\
> + CORRUPTION_ERROR_ACTION(M);\
> + }\
> + }\
> + }\
> + if (XP != 0) {\
> + tbinptr* H = treebin_at(M, X->index);\
> + if (X == *H) {\
> + if ((*H = R) == 0) \
> + clear_treemap(M, X->index);\
> + }\
> + else if (RTCHECK(ok_address(M, XP))) {\
> + if (XP->child[0] == X) \
> + XP->child[0] = R;\
> + else \
> + XP->child[1] = R;\
> + }\
> + else\
> + CORRUPTION_ERROR_ACTION(M);\
> + if (R != 0) {\
> + if (RTCHECK(ok_address(M, R))) {\
> + tchunkptr C0, C1;\
> + R->parent = XP;\
> + if ((C0 = X->child[0]) != 0) {\
> + if (RTCHECK(ok_address(M, C0))) {\
> + R->child[0] = C0;\
> + C0->parent = R;\
> + }\
> + else\
> + CORRUPTION_ERROR_ACTION(M);\
> + }\
> + if ((C1 = X->child[1]) != 0) {\
> + if (RTCHECK(ok_address(M, C1))) {\
> + R->child[1] = C1;\
> + C1->parent = R;\
> + }\
> + else\
> + CORRUPTION_ERROR_ACTION(M);\
> + }\
> + }\
> + else\
> + CORRUPTION_ERROR_ACTION(M);\
> + }\
> + }\
> +}
> +
> +/* Relays to large vs small bin operations */
> +
> +#define insert_chunk(M, P, S)\
> + if (is_small(S)) insert_small_chunk(M, P, S)\
> + else { tchunkptr TP = (tchunkptr)(P); insert_large_chunk(M, TP, S); }
> +
> +#define unlink_chunk(M, P, S)\
> + if (is_small(S)) unlink_small_chunk(M, P, S)\
> + else { tchunkptr TP = (tchunkptr)(P); unlink_large_chunk(M, TP); }
> +
> +
> +/* Relays to internal calls to malloc/free from realloc, memalign etc */
> +
> +#define internal_malloc(m, b) mspace_malloc(m, b)
> +#define internal_free(m, mem) mspace_free(m,mem);
> +
> +
> +/* -------------------------- mspace management --------------------------
> */
> +
> +/* Initialize top chunk and its size */
> +static void init_top(mstate m, mchunkptr p, size_t psize) {
> + /* Ensure alignment */
> + size_t offset = align_offset(chunk2mem(p));
> + p = (mchunkptr)((char*)p + offset);
> + psize -= offset;
> +
> + m->top = p;
> + m->topsize = psize;
> + p->head = psize | PINUSE_BIT;
> + /* set size of fake trailing chunk holding overhead space only once */
> + chunk_plus_offset(p, psize)->head = TOP_FOOT_SIZE;
> +}
> +
> +/* Initialize bins for a new mstate that is otherwise zeroed out */
> +static void init_bins(mstate m) {
> + /* Establish circular links for smallbins */
> + bindex_t i;
> + for (i = 0; i < NSMALLBINS; ++i) {
> + sbinptr bin = smallbin_at(m,i);
> + bin->fd = bin->bk = bin;
> + }
> +}
> +
> +#if PROCEED_ON_ERROR
> +
> +/* default corruption action */
> +static void reset_on_error(mstate m) {
> + int i;
> + ++malloc_corruption_error_count;
> + /* Reinitialize fields to forget about all memory */
> + m->smallbins = m->treebins = 0;
> + m->dvsize = m->topsize = 0;
> + m->seg.base = 0;
> + m->seg.size = 0;
> + m->seg.next = 0;
> + m->top = m->dv = 0;
> + for (i = 0; i < NTREEBINS; ++i)
> + *treebin_at(m, i) = 0;
> + init_bins(m);
> +}
> +#endif /* PROCEED_ON_ERROR */
> +
> +/* Allocate chunk and prepend remainder with chunk in successor base. */
> +static void* prepend_alloc(mstate m, char* newbase, char* oldbase,
> + size_t nb) {
> + mchunkptr p = align_as_chunk(newbase);
> + mchunkptr oldfirst = align_as_chunk(oldbase);
> + size_t psize = (char*)oldfirst - (char*)p;
> + mchunkptr q = chunk_plus_offset(p, nb);
> + size_t qsize = psize - nb;
> + set_size_and_pinuse_of_inuse_chunk(m, p, nb);
> +
> + assert(m->user_data, (char*)oldfirst > (char*)q);
> + assert(m->user_data, pinuse(oldfirst));
> + assert(m->user_data, qsize >= MIN_CHUNK_SIZE);
> +
> + /* consolidate remainder with first chunk of old base */
> + if (oldfirst == m->top) {
> + size_t tsize = m->topsize += qsize;
> + m->top = q;
> + q->head = tsize | PINUSE_BIT;
> + check_top_chunk(m, q);
> + }
> + else if (oldfirst == m->dv) {
> + size_t dsize = m->dvsize += qsize;
> + m->dv = q;
> + set_size_and_pinuse_of_free_chunk(q, dsize);
> + }
> + else {
> + if (!cinuse(oldfirst)) {
> + size_t nsize = chunksize(oldfirst);
> + unlink_chunk(m, oldfirst, nsize);
> + oldfirst = chunk_plus_offset(oldfirst, nsize);
> + qsize += nsize;
> + }
> + set_free_with_pinuse(q, qsize, oldfirst);
> + insert_chunk(m, q, qsize);
> + check_free_chunk(m, q);
> + }
> +
> + check_malloced_chunk(m, chunk2mem(p), nb);
> + return chunk2mem(p);
> +}
> +
> +/* -------------------------- System allocation --------------------------
> */
> +
> +/* Get memory from system using MORECORE or MMAP */
> +static void* sys_alloc(mstate m, size_t nb) {
> + MALLOC_FAILURE_ACTION;
> + return 0;
> +}
> +
> +/* ---------------------------- malloc support ---------------------------
> */
> +
> +/* allocate a large request from the best fitting chunk in a treebin */
> +static void* tmalloc_large(mstate m, size_t nb) {
> + tchunkptr v = 0;
> + size_t rsize = -nb; /* Unsigned negation */
> + tchunkptr t;
> + bindex_t idx;
> + compute_tree_index(nb, idx);
> +
> + if ((t = *treebin_at(m, idx)) != 0) {
> + /* Traverse tree for this bin looking for node with size == nb */
> + size_t sizebits = nb << leftshift_for_tree_index(idx);
> + tchunkptr rst = 0; /* The deepest untaken right subtree */
> + for (;;) {
> + tchunkptr rt;
> + size_t trem = chunksize(t) - nb;
> + if (trem < rsize) {
> + v = t;
> + if ((rsize = trem) == 0)
> + break;
> + }
> + rt = t->child[1];
> + t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1];
> + if (rt != 0 && rt != t)
> + rst = rt;
> + if (t == 0) {
> + t = rst; /* set t to least subtree holding sizes > nb */
> + break;
> + }
> + sizebits <<= 1;
> + }
> + }
> +
> + if (t == 0 && v == 0) { /* set t to root of next non-empty treebin */
> + binmap_t leftbits = left_bits(idx2bit(idx)) & m->treemap;
> + if (leftbits != 0) {
> + bindex_t i;
> + binmap_t leastbit = least_bit(leftbits);
> + compute_bit2idx(leastbit, i);
> + t = *treebin_at(m, i);
> + }
> + }
> +
> + while (t != 0) { /* find smallest of tree or subtree */
> + size_t trem = chunksize(t) - nb;
> + if (trem < rsize) {
> + rsize = trem;
> + v = t;
> + }
> + t = leftmost_child(t);
> + }
> +
> + /* If dv is a better fit, return 0 so malloc will use it */
> + if (v != 0 && rsize < (size_t)(m->dvsize - nb)) {
> + if (RTCHECK(ok_address(m, v))) { /* split */
> + mchunkptr r = chunk_plus_offset(v, nb);
> + assert(m->user_data, chunksize(v) == rsize + nb);
> + if (RTCHECK(ok_next(v, r))) {
> + unlink_large_chunk(m, v);
> + if (rsize < MIN_CHUNK_SIZE)
> + set_inuse_and_pinuse(m, v, (rsize + nb));
> + else {
> + set_size_and_pinuse_of_inuse_chunk(m, v, nb);
> + set_size_and_pinuse_of_free_chunk(r, rsize);
> + insert_chunk(m, r, rsize);
> + }
> + return chunk2mem(v);
> + }
> + }
> + CORRUPTION_ERROR_ACTION(m);
> + }
> + return 0;
> +}
> +
> +/* allocate a small request from the best fitting chunk in a treebin */
> +static void* tmalloc_small(mstate m, size_t nb) {
> + tchunkptr t, v;
> + size_t rsize;
> + bindex_t i;
> + binmap_t leastbit = least_bit(m->treemap);
> + compute_bit2idx(leastbit, i);
> +
> + v = t = *treebin_at(m, i);
> + rsize = chunksize(t) - nb;
> +
> + while ((t = leftmost_child(t)) != 0) {
> + size_t trem = chunksize(t) - nb;
> + if (trem < rsize) {
> + rsize = trem;
> + v = t;
> + }
> + }
> +
> + if (RTCHECK(ok_address(m, v))) {
> + mchunkptr r = chunk_plus_offset(v, nb);
> + assert(m->user_data, chunksize(v) == rsize + nb);
> + if (RTCHECK(ok_next(v, r))) {
> + unlink_large_chunk(m, v);
> + if (rsize < MIN_CHUNK_SIZE)
> + set_inuse_and_pinuse(m, v, (rsize + nb));
> + else {
> + set_size_and_pinuse_of_inuse_chunk(m, v, nb);
> + set_size_and_pinuse_of_free_chunk(r, rsize);
> + replace_dv(m, r, rsize);
> + }
> + return chunk2mem(v);
> + }
> + }
> +
> + CORRUPTION_ERROR_ACTION(m);
> + return 0;
> +}
> +
> +/* --------------------------- realloc support ---------------------------
> */
> +
> +static void* internal_realloc(mstate m, void* oldmem, size_t bytes) {
> + if (bytes >= MAX_REQUEST) {
> + MALLOC_FAILURE_ACTION;
> + return 0;
> + }
> + if (!PREACTION(m)) {
> + mchunkptr oldp = mem2chunk(oldmem);
> + size_t oldsize = chunksize(oldp);
> + mchunkptr next = chunk_plus_offset(oldp, oldsize);
> + mchunkptr newp = 0;
> + void* extra = 0;
> +
> + /* Try to either shrink or extend into top. Else malloc-copy-free */
> +
> + if (RTCHECK(ok_address(m, oldp) && ok_cinuse(oldp) &&
> + ok_next(oldp, next) && ok_pinuse(next))) {
> + size_t nb = request2size(bytes);
> + if (oldsize >= nb) { /* already big enough */
> + size_t rsize = oldsize - nb;
> + newp = oldp;
> + if (rsize >= MIN_CHUNK_SIZE) {
> + mchunkptr remainder = chunk_plus_offset(newp, nb);
> + set_inuse(m, newp, nb);
> + set_inuse(m, remainder, rsize);
> + extra = chunk2mem(remainder);
> + }
> + }
> + else if (next == m->top && oldsize + m->topsize > nb) {
> + /* Expand into top */
> + size_t newsize = oldsize + m->topsize;
> + size_t newtopsize = newsize - nb;
> + mchunkptr newtop = chunk_plus_offset(oldp, nb);
> + set_inuse(m, oldp, nb);
> + newtop->head = newtopsize |PINUSE_BIT;
> + m->top = newtop;
> + m->topsize = newtopsize;
> + newp = oldp;
> + }
> + }
> + else {
> + USAGE_ERROR_ACTION(m, oldmem);
> + POSTACTION(m);
> + return 0;
> + }
> +
> + POSTACTION(m);
> +
> + if (newp != 0) {
> + if (extra != 0) {
> + internal_free(m, extra);
> + }
> + check_inuse_chunk(m, newp);
> + return chunk2mem(newp);
> + }
> + else {
> + void* newmem = internal_malloc(m, bytes);
> + if (newmem != 0) {
> + size_t oc = oldsize - overhead_for(oldp);
> + MEMCPY(newmem, oldmem, (oc < bytes)? oc : bytes);
> + internal_free(m, oldmem);
> + }
> + return newmem;
> + }
> + }
> + return 0;
> +}
> +
> +/* --------------------------- memalign support --------------------------
> */
> +
> +static void* internal_memalign(mstate m, size_t alignment, size_t bytes) {
> + if (alignment <= MALLOC_ALIGNMENT) /* Can just use malloc */
> + return internal_malloc(m, bytes);
> + if (alignment < MIN_CHUNK_SIZE) /* must be at least a minimum chunk size
> */
> + alignment = MIN_CHUNK_SIZE;
> + if ((alignment & (alignment-SIZE_T_ONE)) != 0) {/* Ensure a power of 2 */
> + size_t a = MALLOC_ALIGNMENT << 1;
> + while (a < alignment) a <<= 1;
> + alignment = a;
> + }
> +
> + if (bytes >= MAX_REQUEST - alignment) {
> + if (m != 0) { /* Test isn't needed but avoids compiler warning */
> + MALLOC_FAILURE_ACTION;
> + }
> + }
> + else {
> + size_t nb = request2size(bytes);
> + size_t req = nb + alignment + MIN_CHUNK_SIZE - CHUNK_OVERHEAD;
> + char* mem = (char*)internal_malloc(m, req);
> + if (mem != 0) {
> + void* leader = 0;
> + void* trailer = 0;
> + mchunkptr p = mem2chunk(mem);
> +
> + if (PREACTION(m)) return 0;
> + if ((((size_t)(mem)) % alignment) != 0) { /* misaligned */
> + /*
> + Find an aligned spot inside chunk. Since we need to give
> + back leading space in a chunk of at least MIN_CHUNK_SIZE, if
> + the first calculation places us at a spot with less than
> + MIN_CHUNK_SIZE leader, we can move to the next aligned spot.
> + We've allocated enough total room so that this is always
> + possible.
> + */
> + char* br = (char*)mem2chunk((size_t)(((size_t)(mem +
> + alignment -
> + SIZE_T_ONE)) &
> + -alignment));
> + char* pos = ((size_t)(br - (char*)(p)) >= MIN_CHUNK_SIZE)?
> + br : br+alignment;
> + mchunkptr newp = (mchunkptr)pos;
> + size_t leadsize = pos - (char*)(p);
> + size_t newsize = chunksize(p) - leadsize;
> +
> + /* Otherwise, give back leader, use the rest */
> + set_inuse(m, newp, newsize);
> + set_inuse(m, p, leadsize);
> + leader = chunk2mem(p);
> +
> + p = newp;
> + }
> +
> + assert(m->user_data, chunksize(p) >= nb);
> + assert(m->user_data, (((size_t)(chunk2mem(p))) % alignment) == 0);
> + check_inuse_chunk(m, p);
> + POSTACTION(m);
> + if (leader != 0) {
> + internal_free(m, leader);
> + }
> + if (trailer != 0) {
> + internal_free(m, trailer);
> + }
> + return chunk2mem(p);
> + }
> + }
> + return 0;
> +}
> +
> +/* ----------------------------- user mspaces ----------------------------
> */
> +
> +static mstate init_user_mstate(char* tbase, size_t tsize, void *user_data) {
> + size_t msize = pad_request(sizeof(struct malloc_state));
> + mchunkptr mn;
> + mchunkptr msp = align_as_chunk(tbase);
> + mstate m = (mstate)(chunk2mem(msp));
> + MEMCLEAR(m, msize);
> + INITIAL_LOCK(&m->mutex);
> + msp->head = (msize|PINUSE_BIT|CINUSE_BIT);
> + m->seg.base = m->least_addr = tbase;
> + m->seg.size = m->footprint = m->max_footprint = tsize;
> + m->magic = mparams.magic;
> + m->mflags = mparams.default_mflags;
> + m->user_data = user_data;
> + init_bins(m);
> + mn = next_chunk(mem2chunk(m));
> + init_top(m, mn, (size_t)((tbase + tsize) - (char*)mn) - TOP_FOOT_SIZE);
> + check_top_chunk(m, m->top);
> + return m;
> +}
> +
> +mspace create_mspace_with_base(void* base, size_t capacity, int locked, void
> *user_data) {
> + mstate m = 0;
> + size_t msize = pad_request(sizeof(struct malloc_state));
> + init_mparams(); /* Ensure pagesize etc initialized */
> +
> + if (capacity > msize + TOP_FOOT_SIZE &&
> + capacity < (size_t) -(msize + TOP_FOOT_SIZE + mparams.page_size)) {
> + m = init_user_mstate((char*)base, capacity, user_data);
> + set_lock(m, locked);
> + }
> + return (mspace)m;
> +}
> +
> +/*
> + mspace versions of routines are near-clones of the global
> + versions. This is not so nice but better than the alternatives.
> +*/
> +
> +
> +void* mspace_malloc(mspace msp, size_t bytes) {
> + mstate ms = (mstate)msp;
> + if (!ok_magic(ms)) {
> + USAGE_ERROR_ACTION(ms,ms);
> + return 0;
> + }
> + if (!PREACTION(ms)) {
> + void* mem;
> + size_t nb;
> + if (bytes <= MAX_SMALL_REQUEST) {
> + bindex_t idx;
> + binmap_t smallbits;
> + nb = (bytes < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(bytes);
> + idx = small_index(nb);
> + smallbits = ms->smallmap >> idx;
> +
> + if ((smallbits & 0x3U) != 0) { /* Remainderless fit to a smallbin. */
> + mchunkptr b, p;
> + idx += ~smallbits & 1; /* Uses next bin if idx empty */
> + b = smallbin_at(ms, idx);
> + p = b->fd;
> + assert(ms->user_data, chunksize(p) == small_index2size(idx));
> + unlink_first_small_chunk(ms, b, p, idx);
> + set_inuse_and_pinuse(ms, p, small_index2size(idx));
> + mem = chunk2mem(p);
> + check_malloced_chunk(ms, mem, nb);
> + goto postaction;
> + }
> +
> + else if (nb > ms->dvsize) {
> + if (smallbits != 0) { /* Use chunk in next nonempty smallbin */
> + mchunkptr b, p, r;
> + size_t rsize;
> + bindex_t i;
> + binmap_t leftbits = (smallbits << idx) & left_bits(idx2bit(idx));
> + binmap_t leastbit = least_bit(leftbits);
> + compute_bit2idx(leastbit, i);
> + b = smallbin_at(ms, i);
> + p = b->fd;
> + assert(ms->user_data, chunksize(p) == small_index2size(i));
> + unlink_first_small_chunk(ms, b, p, i);
> + rsize = small_index2size(i) - nb;
> + /* Fit here cannot be remainderless if 4byte sizes */
> + if (SIZE_T_SIZE != 4 && rsize < MIN_CHUNK_SIZE)
> + set_inuse_and_pinuse(ms, p, small_index2size(i));
> + else {
> + set_size_and_pinuse_of_inuse_chunk(ms, p, nb);
> + r = chunk_plus_offset(p, nb);
> + set_size_and_pinuse_of_free_chunk(r, rsize);
> + replace_dv(ms, r, rsize);
> + }
> + mem = chunk2mem(p);
> + check_malloced_chunk(ms, mem, nb);
> + goto postaction;
> + }
> +
> + else if (ms->treemap != 0 && (mem = tmalloc_small(ms, nb)) != 0) {
> + check_malloced_chunk(ms, mem, nb);
> + goto postaction;
> + }
> + }
> + }
> + else if (bytes >= MAX_REQUEST)
> + nb = MAX_SIZE_T; /* Too big to allocate. Force failure (in sys alloc)
> */
> + else {
> + nb = pad_request(bytes);
> + if (ms->treemap != 0 && (mem = tmalloc_large(ms, nb)) != 0) {
> + check_malloced_chunk(ms, mem, nb);
> + goto postaction;
> + }
> + }
> +
> + if (nb <= ms->dvsize) {
> + size_t rsize = ms->dvsize - nb;
> + mchunkptr p = ms->dv;
> + if (rsize >= MIN_CHUNK_SIZE) { /* split dv */
> + mchunkptr r = ms->dv = chunk_plus_offset(p, nb);
> + ms->dvsize = rsize;
> + set_size_and_pinuse_of_free_chunk(r, rsize);
> + set_size_and_pinuse_of_inuse_chunk(ms, p, nb);
> + }
> + else { /* exhaust dv */
> + size_t dvs = ms->dvsize;
> + ms->dvsize = 0;
> + ms->dv = 0;
> + set_inuse_and_pinuse(ms, p, dvs);
> + }
> + mem = chunk2mem(p);
> + check_malloced_chunk(ms, mem, nb);
> + goto postaction;
> + }
> +
> + else if (nb < ms->topsize) { /* Split top */
> + size_t rsize = ms->topsize -= nb;
> + mchunkptr p = ms->top;
> + mchunkptr r = ms->top = chunk_plus_offset(p, nb);
> + r->head = rsize | PINUSE_BIT;
> + set_size_and_pinuse_of_inuse_chunk(ms, p, nb);
> + mem = chunk2mem(p);
> + check_top_chunk(ms, ms->top);
> + check_malloced_chunk(ms, mem, nb);
> + goto postaction;
> + }
> +
> + mem = sys_alloc(ms, nb);
> +
> + postaction:
> + POSTACTION(ms);
> + return mem;
> + }
> +
> + return 0;
> +}
> +
> +void mspace_free(mspace msp, void* mem) {
> + if (mem != 0) {
> + mchunkptr p = mem2chunk(mem);
> +#if FOOTERS
> + mstate fm = get_mstate_for(p);
> +#else /* FOOTERS */
> + mstate fm = (mstate)msp;
> +#endif /* FOOTERS */
> + if (!ok_magic(fm)) {
> + USAGE_ERROR_ACTION(fm, p);
> + return;
> + }
> + if (!PREACTION(fm)) {
> + check_inuse_chunk(fm, p);
> + if (RTCHECK(ok_address(fm, p) && ok_cinuse(p))) {
> + size_t psize = chunksize(p);
> + mchunkptr next = chunk_plus_offset(p, psize);
> + if (!pinuse(p)) {
> + size_t prevsize = p->prev_foot;
> +
> + mchunkptr prev = chunk_minus_offset(p, prevsize);
> + psize += prevsize;
> + p = prev;
> + if (RTCHECK(ok_address(fm, prev))) { /* consolidate backward */
> + if (p != fm->dv) {
> + unlink_chunk(fm, p, prevsize);
> + }
> + else if ((next->head & INUSE_BITS) == INUSE_BITS) {
> + fm->dvsize = psize;
> + set_free_with_pinuse(p, psize, next);
> + goto postaction;
> + }
> + }
> + else
> + goto erroraction;
> + }
> +
> + if (RTCHECK(ok_next(p, next) && ok_pinuse(next))) {
> + if (!cinuse(next)) { /* consolidate forward */
> + if (next == fm->top) {
> + size_t tsize = fm->topsize += psize;
> + fm->top = p;
> + p->head = tsize | PINUSE_BIT;
> + if (p == fm->dv) {
> + fm->dv = 0;
> + fm->dvsize = 0;
> + }
> + goto postaction;
> + }
> + else if (next == fm->dv) {
> + size_t dsize = fm->dvsize += psize;
> + fm->dv = p;
> + set_size_and_pinuse_of_free_chunk(p, dsize);
> + goto postaction;
> + }
> + else {
> + size_t nsize = chunksize(next);
> + psize += nsize;
> + unlink_chunk(fm, next, nsize);
> + set_size_and_pinuse_of_free_chunk(p, psize);
> + if (p == fm->dv) {
> + fm->dvsize = psize;
> + goto postaction;
> + }
> + }
> + }
> + else
> + set_free_with_pinuse(p, psize, next);
> + insert_chunk(fm, p, psize);
> + check_free_chunk(fm, p);
> + goto postaction;
> + }
> + }
> + erroraction:
> + USAGE_ERROR_ACTION(fm, p);
> + postaction:
> + POSTACTION(fm);
> + }
> + }
> +}
> +
> +void* mspace_calloc(mspace msp, size_t n_elements, size_t elem_size) {
> + void* mem;
> + size_t req = 0;
> + mstate ms = (mstate)msp;
> + if (!ok_magic(ms)) {
> + USAGE_ERROR_ACTION(ms,ms);
> + return 0;
> + }
> + if (n_elements != 0) {
> + req = n_elements * elem_size;
> + if (((n_elements | elem_size) & ~(size_t)0xffff) &&
> + (req / n_elements != elem_size))
> + req = MAX_SIZE_T; /* force downstream failure on overflow */
> + }
> + mem = internal_malloc(ms, req);
> + if (mem != 0 && calloc_must_clear(mem2chunk(mem)))
> + MEMCLEAR(mem, req);
> + return mem;
> +}
> +
> +void* mspace_realloc(mspace msp, void* oldmem, size_t bytes) {
> + if (oldmem == 0)
> + return mspace_malloc(msp, bytes);
> +#ifdef REALLOC_ZERO_BYTES_FREES
> + if (bytes == 0) {
> + mspace_free(msp, oldmem);
> + return 0;
> + }
> +#endif /* REALLOC_ZERO_BYTES_FREES */
> + else {
> +#if FOOTERS
> + mchunkptr p = mem2chunk(oldmem);
> + mstate ms = get_mstate_for(p);
> +#else /* FOOTERS */
> + mstate ms = (mstate)msp;
> +#endif /* FOOTERS */
> + if (!ok_magic(ms)) {
> + USAGE_ERROR_ACTION(ms,ms);
> + return 0;
> + }
> + return internal_realloc(ms, oldmem, bytes);
> + }
> +}
> +
> +void* mspace_memalign(mspace msp, size_t alignment, size_t bytes) {
> + mstate ms = (mstate)msp;
> + if (!ok_magic(ms)) {
> + USAGE_ERROR_ACTION(ms,ms);
> + return 0;
> + }
> + return internal_memalign(ms, alignment, bytes);
> +}
> +
> +void mspace_malloc_stats(mspace msp) {
> + mstate ms = (mstate)msp;
> + if (ok_magic(ms)) {
> + internal_malloc_stats(ms);
> + }
> + else {
> + USAGE_ERROR_ACTION(ms,ms);
> + }
> +}
> +
> +size_t mspace_footprint(mspace msp) {
> + size_t result;
> + mstate ms = (mstate)msp;
> + if (ok_magic(ms)) {
> + result = ms->footprint;
> + } else {
> + USAGE_ERROR_ACTION(ms,ms);
> + }
> + return result;
> +}
> +
> +
> +size_t mspace_max_footprint(mspace msp) {
> + size_t result;
> + mstate ms = (mstate)msp;
> + if (ok_magic(ms)) {
> + result = ms->max_footprint;
> + } else {
> + USAGE_ERROR_ACTION(ms,ms);
> + }
> + return result;
> +}
> +
> +
> +#if !NO_MALLINFO
> +struct mallinfo mspace_mallinfo(mspace msp) {
> + mstate ms = (mstate)msp;
> + if (!ok_magic(ms)) {
> + USAGE_ERROR_ACTION(ms,ms);
> + }
> + return internal_mallinfo(ms);
> +}
> +#endif /* NO_MALLINFO */
> +
> +int mspace_mallopt(int param_number, int value) {
> + return change_mparam(param_number, value);
> +}
> +
> diff --git a/qxldod/qxldod.vcxproj b/qxldod/qxldod.vcxproj
> index 749ba1b..f4d279b 100755
> --- a/qxldod/qxldod.vcxproj
> +++ b/qxldod/qxldod.vcxproj
> @@ -279,7 +279,7 @@
> <ItemGroup>
> <ClCompile Include="BaseObject.cpp" />
> <ClCompile Include="driver.cpp" />
> - <ClCompile Include="mspace.c" />
> + <ClCompile Include="mspace.cpp" />
> <ClCompile Include="QxlDod.cpp" />
> </ItemGroup>
> <ItemGroup>
> diff --git a/qxldod/qxldod.vcxproj.filters b/qxldod/qxldod.vcxproj.filters
> index bb9daa9..b0a8103 100755
> --- a/qxldod/qxldod.vcxproj.filters
> +++ b/qxldod/qxldod.vcxproj.filters
> @@ -42,7 +42,7 @@
> <ClCompile Include="QxlDod.cpp">
> <Filter>Source Files</Filter>
> </ClCompile>
> - <ClCompile Include="mspace.c">
> + <ClCompile Include="mspace.cpp">
> <Filter>Source Files</Filter>
> </ClCompile>
> </ItemGroup>
More information about the Spice-devel
mailing list