/* A version of malloc/free/realloc written by Doug Lea and released to the public domain. Send questions/comments/complaints/performance data to dl@cs.oswego.edu VERSION 2.6.1 Sat Dec 2 14:11:12 1995 Doug Lea (dl at gee) * Overview Vital statistics: Alignment: 8-byte Assumed pointer representation: 4 bytes Assumed size_t representation: 4 bytes Minimum wastage per allocated chunk: 4 bytes Maximum wastage per allocated chunk: 24 bytes Minimum allocated size: 16 bytes (12 bytes usable, 4 overhead) Maximum allocated size: 2147483640 (2^31 - 8) bytes Explanations: Malloced chunks have space overhead of 4 bytes for the size field. When a chunk is in use, only the `front' size is used, plus a bit in the NEXT adjacent chunk saying that its previous chunk is in use. When a chunk is freed, 12 additional bytes are needed; 4 for the trailing size field and 8 bytes for free list pointers. Thus, the minimum allocatable size is 16 bytes, of which 12 bytes are usable. 8 byte alignment is currently hardwired into the design. This seems to suffice for all current machines and C compilers. Calling memalign will return a chunk that is both 8-byte aligned and meets the requested (power of two) alignment. Alignnment demands, plus the minimum allocatable size restriction make the worst-case wastage 24 bytes. (Empirically, average wastage is around 5 to 7 bytes.) It is assumed that 32 bits suffice to represent chunk sizes. The maximum size chunk is 2^31 - 8 bytes. malloc(0) returns a pointer to something of the minimum allocatable size. Requests for negative sizes (when size_t is signed) or those greater than (2^31 - 8) bytes will also return a minimum-sized chunk. Structure: This malloc, like any other, is a compromised design. Chunks of memory are maintained using a `boundary tag' method as described in e.g., Knuth or Standish. (See the paper by Paul Wilson ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a survey of such techniques.) Sizes of free chunks are stored both in the front of each chunk and at the end. This makes consolidating fragmented chunks into bigger chunks very fast. The size fields also hold bits representing whether chunks are free or in use. Available chunks are kept in any of three places: * `av': An array of chunks serving as bin headers for consolidated chunks. Each bin is doubly linked. The bins are approximately proportionally (log) spaced. There are a lot of these bins too (128). This may look excessive, but works very well in practice. All procedures maintain the invariant that no consolidated chunk physically borders another one. * `top': The top-most available chunk (i.e., the one bordering the end of available memory) is treated specially. It is never included in any bin, is always kept fully consolidated, is used only if no other chunk is available, and is released back to the system if it is very large (> TRIM_THRESHOLD). * `last_remainder': A bin holding only the remainder of the most recently split (non-top) chunk. This bin is checked before other non-fitting chunks, so as to provide better locality for runs of sequentially allocated chunks. (However, it is only used in this way for `small' requests (< 512 bytes). For larger requests, getting better fits outweighs this.) * Descriptions of public routines malloc: The requested size is first converted into a usable form, `nb'. This currently means to add 4 bytes overhead plus possibly more to obtain 8-byte alignment and/or to obtain a size of at least MINSIZE (currently 16 bytes), the smallest allocatable size. From there, there are five possible ways to allocate a chunk: 1. For small requests (less than 512 bytes), the corresponding bin is scanned, and if a chunk of exactly the right size is found, it is taken. 2. For small requests only, the chunk that was split off as the most recent remaindered chunk is checked, and used if possible. 3. Bins are scanned in increasing size order, using a chunk big enough to fulfill the request, and splitting off any remainder. Bins >= BEST_FIT_THRESHOLD_BIN_NUMBER are searched exaustively, to find the best-fitting chunk. Others are scanned more quickly, in a way approximating LRU order. 4. The chunk bordering the end of memory is split off. 5. New space is obtained from the system using sbrk. Memory is gathered from the system in a way that allows chunks obtained across different sbrk calls to be consolidated, but does not require contiguous memory. Thus, it should be safe to intersperse mallocs with other sbrk calls. free: There are three cases: 1. free(0) has no effect. 2. If a returned chunk borders the current high end of memory, it is consolidated into the top, and if the total unused topmost memory exceeds TRIM_THRESHOLD, malloc_trim is called. The default value of TRIM_THRESHOLD is high enough so that trimming should only occur if the program is maintaining enough unused memory to be worth releasing. 3. Other chunks are consolidated as they arrive, and placed in corresponding bins. realloc: Reallocation proceeds in the usual way. If a chunk can be extended, it is, else a malloc-copy-free sequence is taken. The old unix realloc convention of allowing the last-free'd chunk to be used as an argument to realloc is no longer supported. I don't know of any programs still relying on this feature, and allowing it would also allow too many other incorrect usages of realloc to be sensible. Unless the #define REALLOC_ZERO_BYTES_FREES below is set, realloc with a size argument of zero allocates a minimum-sized chunk. memalign: memalign requests more than enough space from malloc, finds a spot within that chunk that meets the alignment request, and then possibly frees the leading and trailing space. Overreliance on memalign is a sure way to fragment space. valloc: valloc just invokes memalign with alignment argument equal to the page size of the system (or as near to this as can be figured out from all the includes/defines below.) calloc: calloc calls malloc, then zeroes out the allocated chunk. cfree: cfree just calls free. malloc_trim: This routine gives memory back to the system (via negative arguments to sbrk) if there is unused memory at the `high' end of the malloc pool. You can call this after freeing large blocks of memory to potentially reduce the system-level memory requirements of a program. However, it cannot guarantee to reduce memory. Under some allocation patterns, some large free blocks of memory will be locked between two used chunks, so they cannot be given back to the system. malloc_usable_size: This routine tells you how many bytes you can actually use in an allocated chunk, which may be up to 24 bytes more than you requested (although typically much less; often 0). You can use this many bytes without worrying about overwriting other allocated objects. Not a particularly great programming practice, but still sometimes useful. malloc_stats: Prints on stderr the amount of space obtain from the system, the maximum amount (which may be more than current if malloc_trim got called), and the current number of bytes allocated via malloc (or realloc, etc) but not yet freed. * Other implementation notes * Debugging: Because freed chunks may be overwritten with link fields, this malloc will often die when freed memory is overwritten by user programs. This can be very effective (albeit in an annoying way) in helping users track down dangling pointers. If you compile with -DDEBUG, a number of assertion checks are enabled that will catch more memory errors. You probably won't be able to make much sense of the actual assertion errors, but they will at least tell you that you are overwriting memory that you ought not to be. The checking is fairly extensive, and will slow down execution considerably. Calling malloc_stats with DEBUG set will attempt to check every allocated and free chunk in the course of computing the summmaries. Setting DEBUG may also be helpful if you are trying to modify this code. The assertions in the check routines spell out in more detail the assumptions and invariants underlying the code. * Performance differences from previous versions Users of malloc-2.5.X will find that generally, the current version conserves space better, especially when large chunks are allocated. For example, it wastes much less memory when user programs occasionally do things like like allocate space for GIF images amid other requests. Since the current version does not delay consolidation, it is usually faster for mixtures including large chunks, but is (only) sometimes slower when lots of uniform small ones are allocated. For example, the `cfrac' program (see http://www.cs.colorado.edu/~grunwald) runs 2-6% slower (for various test inputs), but uses up to 22% less memory than version 2.5.3 on a Sparc-10. * Concurrency This malloc is NOT designed to work in multithreaded applications. No semaphores or other concurrency control are provided to ensure that multiple malloc or free calls don't run at the same time, which could be disasterous. A single semaphore could be used across malloc, realloc, and free. It would be hard to obtain finer granularity. * Style The implementation is in straight, hand-tuned ANSI C. Among other consequences, it uses a lot of macros. These would be nicer as inlinable procedures, but using macros allows use with non-inlining compiler. Also, because there are so many different twisty paths through malloc steps, the code is not exactly elegant. * History: Based loosely on libg++-1.2X malloc. (It retains some of the overall structure of old version, but most details differ.) Trial version Fri Aug 28 13:14:29 1992 Doug Lea (dl at g.oswego.edu) V2.5 Sat Aug 7 07:41:59 1993 Doug Lea (dl at g.oswego.edu) * removed potential for odd address access in prev_chunk * removed dependency on getpagesize.h * misc cosmetics and a bit more internal documentation * anticosmetics: mangled names in macros to evade debugger strangeness * tested on sparc, hp-700, dec-mips, rs6000 with gcc & native cc (hp, dec only) allowing Detlefs & Zorn comparison study (to appear, SIGPLAN Notices.) V2.5.1 Sat Aug 14 15:40:43 1993 Doug Lea (dl at g) * faster bin computation & slightly different binning * merged all consolidations to one part of malloc proper (eliminating old malloc_find_space & malloc_clean_bin) * Scan 2 returns chunks (not just 1) Sat Apr 2 06:51:25 1994 Doug Lea (dl at g) * Propagate failure in realloc if malloc returns 0 * Add stuff to allow compilation on non-ANSI compilers from kpv@research.att.com V2.5.2 Tue Apr 5 16:20:40 1994 Doug Lea (dl at g) * realloc: try to expand in both directions * malloc: swap order of clean-bin strategy; * realloc: only conditionally expand backwards * Try not to scavenge used bins * Use bin counts as a guide to preallocation * Occasionally bin return list chunks in first scan * Add a few optimizations from colin@nyx10.cs.du.edu V2.5.3 Tue Apr 26 10:16:01 1994 Doug Lea (dl at g) V2.5.4 Wed Nov 1 07:54:51 1995 Doug Lea (dl at gee) * Added malloc_trim, with help from Wolfram Gloger (wmglo@Dent.MED.Uni-Muenchen.DE). V2.6.0 Sat Nov 4 07:05:23 1995 Doug Lea (dl at gee) * Removed footers when chunks are in use. Thanks to Paul Wilson (wilson@cs.texas.edu) for the suggestion. V2.6.1 Sat Dec 2 14:10:57 1995 Doug Lea (dl at gee) * Re-tuned and fixed to behave more nicely with above two changes. * Removed all preallocation code since under current scheme the work required to undo bad preallocations exceeds the work saved in good cases for most test programs. * No longer use return list or unconsolidated bins since no scheme using them consistently outperforms those that don't given above changes. * Use best fit for very large chunks to prevent some worst-cases. * Added some support for debugging */ /* TUNABLE PARAMETERS */ /* SBRK_UNIT is a good size to call sbrk with. It should normally be system page size or a multiple thereof. If sbrk is very slow on a system, it pays to increase this. Otherwise, it should not matter too much. Also, if a program needs a certain minimum amount of memory, this amount can be malloc'ed then immediately free'd before starting to avoid calling sbrk so often. (At least so long as it is < TRIM_THRESHOLD; else it will be released.) */ #ifndef SBRK_UNIT #define SBRK_UNIT 8192 #endif /* TRIM_THRESHOLD is the maximum amount of unused trailing memory to keep before releasing via malloc_trim in free(). Must be greater than SBRK_UNIT to have any useful effect. Default value of 256K appears to be a good compromise for the slowness of sbrk with negative arguments on most systems. To disable trimming completely, you can set to ((unsigned long)(-1)) */ #ifndef TRIM_THRESHOLD #define TRIM_THRESHOLD (256 * 1024) #endif /* Chunks in bins >= BEST_FIT_THRESHOLD are scanned strictly by size order rather than in a LRU fashion. This can be much more time consuming, but can save space. Empirically it is worth it only for very large chunks. Minimally, the topmost bin (#126) should be scanned via best-fit to alleviate fragmentation of the largest possible representable chunks. Because this is used in inner scan loops, the value has to be expressed as a bin. See the table of bin values below. The default value uses best fit for requests >= 64K bytes. */ #ifndef BEST_FIT_THRESHOLD_BIN_NUMBER #define BEST_FIT_THRESHOLD_BIN_NUMBER 121 #endif /* REALLOC_ZERO_BYTES_FREES should be set if a call to realloc with zero bytes should be the same as a call to free. Some people think it should. Otherwise, since this malloc returns a unique pointer for malloc(0), so does realloc(p, 0). */ /* #define REALLOC_ZERO_BYTES_FREES */ /* HAVE_MEMCPY should be defined if you are not otherwise using ANSI STD C, but still have memcpy and memset in your C library and want to use them. By default defined. */ #define HAVE_MEMCPY /* preliminaries */ #ifndef __STD_C #ifdef __STDC__ #define __STD_C 1 #else #if __cplusplus #define __STD_C 1 #else #define __STD_C 0 #endif /*__cplusplus*/ #endif /*__STDC__*/ #endif /*__STD_C*/ #ifndef Void_t #if __STD_C #define Void_t void #else #define Void_t char #endif #endif /*Void_t*/ #if __STD_C #include /* for size_t */ #else #include #endif #include /* needed for malloc_stats */ #if DEBUG #include #else #define assert(x) ((void)0) #endif #ifdef __cplusplus extern "C" { #endif #if __STD_C extern Void_t* sbrk(ptrdiff_t); #else extern Void_t* sbrk(); #endif /* how to zero out and copy memory (needed in calloc, realloc) */ #if defined(__STD_C) || defined(HAVE_MEMCPY) void* memset(void*, int, size_t); void* memcpy(void*, const void*, size_t); #define MALLOC_ZERO(charp, nbytes) memset(charp, 0, nbytes) #define MALLOC_COPY(dest,src,nbytes) memcpy((dest), (src), (nbytes)) #else /* We only invoke with multiples of size_t units, with size_t alignment */ #define MALLOC_ZERO(charp, nbytes) \ { \ size_t* mzp = (size_t*)(charp); \ size_t mzn = (nbytes) / sizeof(size_t); \ while (mzn-- > 0) *mzp++ = 0; \ } #define MALLOC_COPY(dest,src,nbytes) \ { \ size_t* mcsrc = (size_t*) src; \ size_t* mcdst = (size_t*) dest; \ long mcn = (nbytes) / sizeof(size_t); \ while (mcn-- > 0) *mcdst++ = *mcsrc++; \ } #endif /* mechanics for getpagesize; adapted from bsd/gnu getpagesize.h */ #if defined(BSD) || defined(DGUX) || defined(HAVE_GETPAGESIZE) extern size_t getpagesize(); # define malloc_getpagesize getpagesize() #else # include # ifdef EXEC_PAGESIZE # define malloc_getpagesize EXEC_PAGESIZE # else # ifdef NBPG # ifndef CLSIZE # define malloc_getpagesize NBPG # else # define malloc_getpagesize (NBPG * CLSIZE) # endif # else # ifdef NBPC # define malloc_getpagesize NBPC # else # define malloc_getpagesize SBRK_UNIT /* just guess */ # endif # endif # endif #endif /* Declarations of public routines defined in this file */ #if __STD_C Void_t* malloc(size_t); void free(Void_t*); Void_t* realloc(Void_t*, size_t); Void_t* memalign(size_t, size_t); Void_t* valloc(size_t); Void_t* calloc(size_t, size_t); void cfree(Void_t*); int malloc_trim(); size_t malloc_usable_size(Void_t*); void malloc_stats(); #else Void_t* malloc(); void free(); Void_t* realloc(); Void_t* memalign(); Void_t* valloc(); Void_t* calloc(); void cfree(); int malloc_trim(); size_t malloc_usable_size(); void malloc_stats(); #endif #ifdef __cplusplus }; /* end of extern "C" */ #endif /* CHUNKS */ struct malloc_chunk { size_t size; /* Size in bytes, including overhead. */ struct malloc_chunk* fd; /* double links -- used only if free. */ struct malloc_chunk* bk; size_t unused; /* to pad decl to min chunk size */ }; /* size field is or'ed with PREV_INUSE when previous adjacent chunk in use*/ #define PREV_INUSE 0x1 typedef struct malloc_chunk* mchunkptr; /* sizes, alignments */ #define SIZE_SZ (sizeof(size_t)) #define MALLOC_ALIGN_MASK (SIZE_SZ + SIZE_SZ - 1) #define MINSIZE (sizeof(struct malloc_chunk)) /* pad request bytes into a usable size */ #define request2size(req) \ (((long)(req) < MINSIZE - SIZE_SZ) ? MINSIZE : \ (((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~(MALLOC_ALIGN_MASK))) /* Check if m has acceptable alignment */ #define aligned_OK(m) (((size_t)((m)) & (MALLOC_ALIGN_MASK)) == 0) /* Physical chunk operations */ /* Ptr to next physical malloc_chunk. */ #define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->size & ~PREV_INUSE) )) /* Ptr to previous physical malloc_chunk */ #define prev_chunk(p)\ ((mchunkptr)( ((char*)(p)) - *((size_t*)((char*)(p) - SIZE_SZ)))) /* Treat space at ptr + offset as a chunk */ #define chunk_at_offset(p, s) ((mchunkptr)(((char*)(p)) + (s))) /* conversion from malloc headers to user pointers, and back */ #define chunk2mem(p) ((Void_t*)((char*)(p) + SIZE_SZ)) #define mem2chunk(mem) ((mchunkptr)((char*)(mem) - SIZE_SZ)) /* Dealing with use bits */ /* extract p's inuse bit */ #define inuse(p)\ ((((mchunkptr)(((char*)(p))+((p)->size & ~PREV_INUSE)))->size) & PREV_INUSE) /* extract inuse bit of previous chunk */ #define prev_inuse(p) ((p)->size & PREV_INUSE) /* set/clear chunk as in use without otherwise disturbing */ #define set_inuse(p)\ ((mchunkptr)(((char*)(p)) + ((p)->size & ~PREV_INUSE)))->size |= PREV_INUSE #define clear_inuse(p)\ ((mchunkptr)(((char*)(p)) + ((p)->size & ~PREV_INUSE)))->size &= ~(PREV_INUSE) /* set/clear inuse bits in known places */ #define set_inuse_bit_at_offset(p, s)\ (((mchunkptr)(((char*)(p)) + (s)))->size |= PREV_INUSE) #define clear_inuse_bit_at_offset(p, s)\ (((mchunkptr)(((char*)(p)) + (s)))->size &= ~(PREV_INUSE)) /* Dealing with size fields */ /* Get size, ignoring use bits */ #define chunksize(p) ((p)->size & ~PREV_INUSE) /* Set size at head, without disturbing its use bit */ #define set_head_size(p, s) ((p)->size = (((p)->size & PREV_INUSE) | (s))) /* Set size/use ignoring previous bits in header */ #define set_head(p, s) ((p)->size = (s)) /* Set size at footer (only when chunk is not in use) */ #define set_foot_size(p, s) (*((size_t*)((char*)(p) + (s) - SIZE_SZ)) = (s)) /* place size at front and back of chunk, preserving use bits on front size */ #define set_sizes(p, s) { set_head_size(p, s); set_foot_size(p, s); } /* BINS and related static data */ /* The bins, `av' are just an array of chunks, each having its fd/bk pointers serving as the head of a doubly-linked list of chunks. Bins are initialized to just point to themselves, representing empty lists. A one-level index structure is placed on top of the bins. (This helps compensate for large numbers of bins.) `binblocks' is a one-word bitvector recording whether groups of BINBLOCKWIDTH bins have any (possibly) non-empty bins, so they can be skipped over all at once during during traversals. The bits are NOT always cleared as soon as all bins in a block are empty, but instead only when all are noticed to be empty during traversal in malloc. The first 2 and last 1 av cells are never indexed, but are instead used for bookkeeping. This is not to save space, but to simplify indexing, maintain locality, and avoid some initialization tests. (For example, because top initially points to its own bin with a zero size, which can be inspected but never used, we avoid having to check to see whether it even exists yet.) */ typedef struct malloc_chunk* mbinptr; #define NAV 128 /* number of normal bins */ #define BINBLOCKWIDTH 4 /* bins per block */ /* Special bins/fields: */ #define top (av[0].fd) /* The topmost chunk */ #define binblocks (av[0].size) /* bitvector of nonempty blocks */ #define last_remainder (&(av[1])) /* remainder from last split chunk */ #define best_fit_threshhold (&(av[BEST_FIT_THRESHOLD_BIN_NUMBER])) /* Helper macros to initialize bins */ #define IAV(i) { 0, &(av[i]), &(av[i]), 0 } static struct malloc_chunk av[NAV] = { IAV(0), IAV(1), IAV(2), IAV(3), IAV(4), IAV(5), IAV(6), IAV(7), IAV(8), IAV(9), IAV(10), IAV(11), IAV(12), IAV(13), IAV(14), IAV(15), IAV(16), IAV(17), IAV(18), IAV(19), IAV(20), IAV(21), IAV(22), IAV(23), IAV(24), IAV(25), IAV(26), IAV(27), IAV(28), IAV(29), IAV(30), IAV(31), IAV(32), IAV(33), IAV(34), IAV(35), IAV(36), IAV(37), IAV(38), IAV(39), IAV(40), IAV(41), IAV(42), IAV(43), IAV(44), IAV(45), IAV(46), IAV(47), IAV(48), IAV(49), IAV(50), IAV(51), IAV(52), IAV(53), IAV(54), IAV(55), IAV(56), IAV(57), IAV(58), IAV(59), IAV(60), IAV(61), IAV(62), IAV(63), IAV(64), IAV(65), IAV(66), IAV(67), IAV(68), IAV(69), IAV(70), IAV(71), IAV(72), IAV(73), IAV(74), IAV(75), IAV(76), IAV(77), IAV(78), IAV(79), IAV(80), IAV(81), IAV(82), IAV(83), IAV(84), IAV(85), IAV(86), IAV(87), IAV(88), IAV(89), IAV(90), IAV(91), IAV(92), IAV(93), IAV(94), IAV(95), IAV(96), IAV(97), IAV(98), IAV(99), IAV(100), IAV(101), IAV(102), IAV(103), IAV(104), IAV(105), IAV(106), IAV(107), IAV(108), IAV(109), IAV(110), IAV(111), IAV(112), IAV(113), IAV(114), IAV(115), IAV(116), IAV(117), IAV(118), IAV(119), IAV(120), IAV(121), IAV(122), IAV(123), IAV(124), IAV(125), IAV(126), IAV(127) }; /* Other static bookkeeping data */ /* The total memory obtained from system via sbrk */ static size_t sbrked_mem = 0; /* The maximum memory obtained from system via sbrk */ static size_t max_sbrked_mem = 0; /* The first value returned from sbrk */ static char* sbrk_base = (char*)(-1); /* Operations on bins and bin lists */ /* Indexing into bins Bins are log-spaced: 64 bins of size 8 32 bins of size 64 16 bins of size 512 8 bins of size 4096 4 bins of size 32768 2 bins of size 262144 1 bin of size what's left There is actually a little bit of slop in the numbers in findbin() for the sake of speed. This makes no difference elsewhere. */ #define bin_index(sz) \ (((((unsigned long)(sz)) >> 9) == 0) ? (((unsigned long)(sz)) >> 3): \ ((((unsigned long)(sz)) >> 9) <= 4) ? 56 + (((unsigned long)(sz)) >> 6): \ ((((unsigned long)(sz)) >> 9) <= 20) ? 91 + (((unsigned long)(sz)) >> 9): \ ((((unsigned long)(sz)) >> 9) <= 84) ? 110 + (((unsigned long)(sz)) >> 12): \ ((((unsigned long)(sz)) >> 9) <= 340) ? 119 + (((unsigned long)(sz)) >> 15): \ ((((unsigned long)(sz)) >> 9) <= 1364) ? 124 + (((unsigned long)(sz)) >> 18): \ 126) /* bins for chunks < 512 are all spaced 8 bytes apart, and hold identically sized chunks. This is exploited in malloc. */ #define MAX_SMALLBIN_SIZE 512 #define SMALLBIN_WIDTH 8 #define smallbin_index(sz) (((unsigned long)(sz)) >> 3) /* field-extraction macros */ #define first(b) ((b)->fd) #define last(b) ((b)->bk) /* bin<->block macros */ #define idx2binblock(ix) (1 << (ix / BINBLOCKWIDTH)) #define mark_binblock(ii) (binblocks |= idx2binblock(ii)) #define clear_binblock(ii) (binblocks &= ~(idx2binblock(ii))) /* link p at front of b -- used for consolidated chunks */ #define frontlink(b, p) \ { \ mchunkptr Fbl = (b)->fd; \ (p)->bk = (b); \ (p)->fd = Fbl; \ Fbl->bk = (b)->fd = (p); \ } /* link p at back of b -- used for remaindered chunks */ #define backlink(b, p) \ { \ mchunkptr Bbl = (b)->bk; \ (p)->fd = (b); \ (p)->bk = Bbl; \ Bbl->fd = (b)->bk = (p); \ } /* take a chunk off a list */ #define unlink(p) \ { \ mchunkptr Bul = (p)->bk; \ mchunkptr Ful = (p)->fd; \ Ful->bk = Bul; Bul->fd = Ful; \ } \ /* Debugging support */ #if DEBUG #if __STD_C static void do_check_chunk(mchunkptr p) #else static void do_check_chunk(p) mchunkptr p; #endif { size_t sz = p->size & ~PREV_INUSE; assert((long)sz >= MINSIZE); assert((((size_t)((char*)(p) + SIZE_SZ)) & MALLOC_ALIGN_MASK) == 0); assert((char*)p >= sbrk_base); assert((char*)p + sz <= sbrk_base + sbrked_mem); assert(prev_inuse(top)); } #if __STD_C static void do_check_free_chunk(mchunkptr p) #else static void do_check_free_chunk(p) mchunkptr p; #endif { size_t sz = p->size & ~PREV_INUSE; mchunkptr next = chunk_at_offset(p, sz); do_check_chunk(p); assert(*((size_t*)((char*)(p) + sz - SIZE_SZ)) == sz); assert(!inuse(p)); assert(prev_inuse(p)); assert (next == top || inuse(next)); assert(p->fd->bk == p); assert(p->bk->fd == p); assert((char*)p < (char*)top); } #if __STD_C static void do_check_inuse_chunk(mchunkptr p) #else static void do_check_inuse_chunk(p) mchunkptr p; #endif { do_check_chunk(p); assert(inuse(p)); if (!prev_inuse(p)) { mchunkptr prv = prev_chunk(p); assert(next_chunk(prv) == p); } assert((char*)p < (char*)top); } #if __STD_C static void do_check_malloced_chunk(mchunkptr p, size_t s) #else static void do_check_malloced_chunk(p, s) mchunkptr p; size_t s; #endif { long room = chunksize(p) - s; assert(room >= 0); assert(room < MINSIZE); do_check_inuse_chunk(p); } #define check_free_chunk(P) do_check_free_chunk(P) #define check_inuse_chunk(P) do_check_inuse_chunk(P) #define check_chunk(P) do_check_chunk(P) #define check_malloced_chunk(P,N) do_check_malloced_chunk(P,N) #else #define check_free_chunk(P) #define check_inuse_chunk(P) #define check_chunk(P) #define check_malloced_chunk(P,N) #endif /* Utility : extend top chunk by calling sbrk for at least nb bytes */ #if __STD_C static Void_t* malloc_extend_top(size_t nb) #else static Void_t* malloc_extend_top(nb) size_t nb; #endif { size_t end; /* Find a good size to ask sbrk for. Minimally, we need to pad with enough space to hit alignments and have a MINSIZE remainder left from this malloc call. */ size_t sbrk_size = ((nb + SBRK_UNIT + 3 * MINSIZE) / SBRK_UNIT) * SBRK_UNIT; char* cp = (char*)(sbrk(sbrk_size)); if (cp == (char*)(-1)) return 0; /* sbrk returns -1 on failure */ if (sbrk_base == (char*)(-1)) sbrk_base = cp; /* We need at least SIZE_SZ byte alignment. If not, try again. */ end = ((size_t)cp) + sbrk_size; if ((end & (SIZE_SZ - 1)) != 0) { size_t correction = end - (end & (SIZE_SZ - 1)); char* newcp = (char*)sbrk(correction); /* If we can't get extra bytes, must die. */ if (newcp == (char*)-1) return 0; sbrk_size += correction; } sbrked_mem += sbrk_size; if (sbrked_mem > max_sbrked_mem) max_sbrked_mem = sbrked_mem; if (cp != (char*)(next_chunk(top))) { /* It's either first time through or someone else called sbrk. */ /* Possibly waste a few bytes so that user chunks will be aligned */ mchunkptr old_top = top; size_t* ip = (size_t*)cp; while (!aligned_OK(chunk2mem(ip))) { *ip++ = PREV_INUSE; /* mark as 0-sized chunk so can't be used */ sbrk_size -= SIZE_SZ; } top = (mchunkptr)ip; set_head(top, sbrk_size | PREV_INUSE); /* if old top exists, release it */ if ((long)(chunksize(old_top)) >= (long)MINSIZE) { set_inuse(old_top); free(chunk2mem(old_top)); } } else /* Just extend the previous top chunk. */ { size_t topsize = sbrk_size + chunksize(top); set_head(top, topsize | PREV_INUSE); } return top; } /* Main public routines */ #if __STD_C Void_t* malloc(size_t bytes) #else Void_t* malloc(bytes) size_t bytes; #endif { mbinptr bin; /* bin traverser */ int idx; /* bin index */ unsigned long block; /* block traverser bit */ mchunkptr lr; /* last remainder from split */ size_t nb = request2size(bytes); /* padded request size; */ /* Special processing for small requests */ if (nb < MAX_SMALLBIN_SIZE - SMALLBIN_WIDTH) /* ( `- SM...' to test 2 bins) */ { mchunkptr victim; idx = smallbin_index(nb); bin = &(av[idx]); /* Fast check for own bin -- no traversal or size check necessary. */ /* Also, the next one, since it would have a remainder < MINSIZE */ if ( ((victim = last(bin)) != bin) || ((victim = last(bin+1)) != bin+1)) { unlink(victim); set_inuse(victim); check_malloced_chunk(victim, nb); return chunk2mem(victim); } else { idx += 2; /* Prepare for loop below -- we've already scanned 2 bins */ /* Try to use the last split-off remainder. */ if ( (lr = last_remainder->fd) != last_remainder) { long room = chunksize(lr) - nb; if (room >= 0) { victim = lr; if (room >= MINSIZE) /* shrink the remainder */ { lr = chunk_at_offset(victim, nb); set_head_size(victim, nb); set_head(lr, room | PREV_INUSE); lr->fd = lr->bk = last_remainder; set_foot_size(lr, room); last_remainder->fd = last_remainder->bk = lr; } else /* exhaust it */ { set_inuse_bit_at_offset(victim, nb + room); last_remainder->fd = last_remainder->bk = last_remainder; } check_malloced_chunk(victim, nb); return chunk2mem(victim); } } } } else { idx = bin_index(nb); lr = last_remainder->fd; } /* Get rid of last remainder, either because we couldn't use it for a small request, or have a large request, in which case we want to use it only if it is found in bin scan. */ if (lr != last_remainder) { size_t lrsize = chunksize(lr); int lr_bin_index = bin_index(lrsize); mbinptr lr_bin = &(av[lr_bin_index]); backlink(lr_bin, lr); mark_binblock(lr_bin_index); last_remainder->fd = last_remainder->bk = last_remainder; } /* Main bin scan */ block = idx2binblock(idx); if (block <= binblocks) /* if there are any possibly nonempty blocks ... */ { unsigned long bb = binblocks; /* Cache as local */ /* get to first possibly nonempty block */ if ( (block & bb) == 0) { /* force to an even block boundary */ bin = &(av[(idx & ~(BINBLOCKWIDTH - 1)) + BINBLOCKWIDTH]); block <<= 1; while ((block & bb) == 0) { bin += BINBLOCKWIDTH; block <<= 1; } } else bin = &(av[idx]); for (;;) /* for each possibly nonempty block ... */ { int bincount = BINBLOCKWIDTH; /* count empty bins to clear bit */ do /* for each bin in this block ... */ { mchunkptr p = last(bin); if (p != bin) /* if non-empty ... */ { mchunkptr victim = 0; long remainder_size = 0; if (bin >= best_fit_threshhold) { do /* scan best-fit style */ { long room = chunksize(p) - nb; if (room >= 0 && (victim == 0 || room < remainder_size)) { victim = p; remainder_size = room; if (remainder_size < MINSIZE) break; } } while ( (p = p->bk) != bin); } else { do /* scan back (= older) to front, take first that fits */ { remainder_size = chunksize(p) - nb; if (remainder_size >= 0) { victim = p; break; } } while ( (p = p->bk) != bin); } if (victim != 0) { check_free_chunk(victim); unlink(victim); if (remainder_size >= MINSIZE) /* place in last remainder */ { mchunkptr remainder = chunk_at_offset(victim, nb); set_head_size(victim, nb); set_head(remainder, remainder_size | PREV_INUSE); remainder->fd = remainder->bk = last_remainder; set_foot_size(remainder, remainder_size); last_remainder->fd = last_remainder->bk = remainder; } else set_inuse_bit_at_offset(victim, nb + remainder_size); check_malloced_chunk(victim, nb); return chunk2mem(victim); } else bincount = -1; /* disable bit clear below */ } else --bincount; ++bin; } while ( ((bin - av) % BINBLOCKWIDTH) != 0); /* Clear out the block bit. */ if (bincount > 0) /* backtrack to try to clear a partial block */ { mbinptr t = bin - BINBLOCKWIDTH; while (last(t) == t && --bincount > 0) ++t; } if (bincount == 0) binblocks = bb &= ~block; /* Get to the next possibly nonempty block */ if ( (block <<= 1) <= bb && (block != 0) ) { while ((block & bb) == 0) { bin += BINBLOCKWIDTH; block <<= 1; } } else break; } } /* If fall though, use top chunk */ { mchunkptr victim = top; long new_top_size = chunksize(victim) - nb; /* Require that there be a remainder (simplifies other processing) */ if (new_top_size < (long)MINSIZE) { victim = malloc_extend_top(nb); if (victim == 0) return 0; /* propagate sbrk failure */ else new_top_size = chunksize(victim) - nb; } set_head_size(victim, nb); top = chunk_at_offset(victim, nb); set_head(top, new_top_size | PREV_INUSE); check_malloced_chunk(victim, nb); return chunk2mem(victim); } } #if __STD_C void free(Void_t* mem) #else void free(mem) Void_t* mem; #endif { if (mem != 0) /* free(0) has no effect */ { mchunkptr p = mem2chunk(mem); size_t sz = chunksize(p); mchunkptr next; check_inuse_chunk(p); if (!prev_inuse(p)) /* consolidate backward */ { mchunkptr previous = prev_chunk(p); sz += chunksize(previous); unlink(previous); p = previous; } next = chunk_at_offset(p, sz); if (next == top) /* merge with top */ { sz += chunksize(next); set_head(p, sz | PREV_INUSE); top = p; /* If top is too big, call malloc_trim */ if ((unsigned long)sz >= (unsigned long)TRIM_THRESHOLD) malloc_trim(); } else /* Place in a bin */ { mbinptr bin; int idx; clear_inuse_bit_at_offset(p, sz); if (!inuse(next)) /* consolidate forward */ { sz += chunksize(next); unlink(next); } set_sizes(p, sz); idx = bin_index(sz); mark_binblock(idx); bin = &(av[idx]); frontlink(bin, p); check_free_chunk(p); } } } #if __STD_C Void_t* realloc(Void_t* oldmem, size_t bytes) #else Void_t* realloc(oldmem, bytes) Void_t* oldmem; size_t bytes; #endif { size_t nb; mchunkptr oldp; size_t oldsize; mchunkptr newp; size_t newsize; #if REALLOC_ZERO_BYTES_FREES if (bytes == 0) { free(oldmem); return 0; } #endif /* realloc of null is supposed to be same as malloc */ if (oldmem == 0) return malloc(bytes); newp = oldp = mem2chunk(oldmem); newsize = oldsize = chunksize(oldp); check_inuse_chunk(oldp); nb = request2size(bytes); if ((long)(oldsize) < (long)(nb)) { mchunkptr next = chunk_at_offset(oldp, oldsize); size_t nextsize; Void_t* newmem; /* Expand forward into top only if there will be a remainder */ if (next == top) { nextsize = chunksize(next); if ((long)(nextsize + newsize) >= (long)(nb + MINSIZE)) { newsize += nextsize; top = chunk_at_offset(oldp, nb); set_head(top, (newsize - nb) | PREV_INUSE); set_head_size(oldp, nb); check_malloced_chunk(oldp, nb); return chunk2mem(oldp); } else next = 0; /* disable use below */ } else if (!inuse(next)) /* expand forward */ { nextsize = chunksize(next); if (((long)(nextsize + newsize) >= (long)nb)) { unlink(next); newsize += nextsize; goto split; } } else /* disable use below */ { next = 0; nextsize = 0; } if (!prev_inuse(oldp)) { mchunkptr prev = prev_chunk(oldp); size_t prevsize = chunksize(prev); if (prevsize < nb) /* otherwise we are better off re-mallocing */ { /* shift backward */ if ((long)(prevsize + newsize) >= (long)nb) { unlink(prev); newp = prev; newsize += prevsize; newmem = chunk2mem(newp); MALLOC_COPY(newmem, oldmem, oldsize - SIZE_SZ); goto split; } /* forward + backward */ else if (next != 0 && (long)(nextsize + prevsize + newsize) >= (long)nb) { unlink(next); unlink(prev); newp = prev; newsize += nextsize + prevsize; newmem = chunk2mem(newp); MALLOC_COPY(newmem, oldmem, oldsize - SIZE_SZ); goto split; } } } /* Must allocate */ newmem = malloc(bytes); if (newmem == 0) return 0; /* propagate failure */ else { newp = mem2chunk(newmem); /* Avoid copy if newp is next chunk after oldp. */ /* (This can only happen when new chunk is sbrk'ed.) */ if (newp == next_chunk(oldp)) { newsize += chunksize(newp); newp = oldp; goto split; } else { MALLOC_COPY(newmem, oldmem, oldsize - SIZE_SZ); free(oldmem); check_malloced_chunk(newp, nb); return newmem; } } } split: /* split off extra room in old or expanded chunk */ if (newsize - nb >= MINSIZE) /* split off remainder */ { mchunkptr remainder = chunk_at_offset(newp, nb); size_t remainder_size = newsize - nb; set_head_size(newp, nb); set_head(remainder, remainder_size | PREV_INUSE); set_inuse_bit_at_offset(remainder, remainder_size); free(chunk2mem(remainder)); /* let free() deal with it */ } else { set_head_size(newp, newsize); set_inuse_bit_at_offset(newp, newsize); } check_malloced_chunk(newp, nb); return chunk2mem(newp); } /* Return a pointer to space with at least the alignment requested */ /* Alignment argument must be a power of two */ #if __STD_C Void_t* memalign(size_t alignment, size_t bytes) #else Void_t* memalign(alignment, bytes) size_t alignment; size_t bytes; #endif { mchunkptr p; /* Use an alignment that both we and the user can live with: */ size_t align = (alignment > MINSIZE) ? alignment : MINSIZE; /* Call malloc with worst case padding to hit alignment; */ size_t nb = request2size(bytes); char* m = (char*)(malloc(nb + align + MINSIZE)); if (m == 0) return 0; /* propagate failure */ p = mem2chunk(m); if ((((size_t)(m)) % align) != 0) /* misaligned */ { mchunkptr newp; size_t leadsize; size_t newsize; /* Find an aligned spot inside chunk. Since we need to give back leading space in a chunk of at least MINSIZE, if the first calculation places us at a spot with less than MINSIZE leader, we can move to the next aligned spot -- we've allocated enough total room so that this is always possible. */ char* cp = (char*) ( (((size_t)(m + align - 1)) & -align) - SIZE_SZ ); if ((long)(cp - (char*)(p)) < MINSIZE) cp = cp + align; newp = (mchunkptr)cp; leadsize = cp - (char*)(p); newsize = chunksize(p) - leadsize; /* give back leader, use the rest */ set_head(newp, newsize | PREV_INUSE); set_inuse_bit_at_offset(newp, newsize); set_head_size(p, leadsize); free(chunk2mem(p)); p = newp; } /* Also give back spare room at the end */ if ((long)(chunksize(p) - nb) >= (long)MINSIZE) { size_t remainder_size = chunksize(p) - nb; mchunkptr remainder = chunk_at_offset(p, nb); set_head(remainder, remainder_size | PREV_INUSE); set_head_size(p, nb); free(chunk2mem(remainder)); } check_malloced_chunk(p, nb); return chunk2mem(p); } /* Derivatives */ #if __STD_C Void_t* valloc(size_t bytes) #else Void_t* valloc(bytes) size_t bytes; #endif { /* Cache result of getpagesize */ static size_t malloc_pagesize = 0; if (malloc_pagesize == 0) malloc_pagesize = malloc_getpagesize; return memalign (malloc_pagesize, bytes); } #if __STD_C Void_t* calloc(size_t n, size_t elem_size) #else Void_t* calloc(n, elem_size) size_t n; size_t elem_size; #endif { size_t sz = n * elem_size; Void_t* mem = malloc(sz); if (mem == 0) return 0; else { mchunkptr p = mem2chunk(mem); size_t csz = chunksize(p); MALLOC_ZERO(mem, csz - SIZE_SZ); return mem; } } #if __STD_C void cfree(Void_t *mem) #else void cfree(mem) Void_t *mem; #endif { free(mem); } /* Non-standard routines */ /* If possible, release memory back to the system. Return 1 if successful */ int malloc_trim() { /* Can only release top-most memory. We only release multiples of SBRK_UNIT, and guarantee there is a unit left to handle alignment gaps and a minimal remainder chunk. */ size_t topsize = chunksize(top); long units = (topsize + SBRK_UNIT - 1 - 2 * MINSIZE) / SBRK_UNIT - 1; if (units < 1) /* Not enough memory to release */ return 0; else { /* Test to make sure no one else called sbrk */ char* current_sbrk = (char*)(sbrk(0)); if (current_sbrk != (char*)(top) + topsize) return 0; /* Apparently we don't own memory; must fail */ else { long sbrk_size = units * SBRK_UNIT; char* cp = (char*)(sbrk(-sbrk_size)); if (cp == (char*)(-1)) /* sbrk failed? */ { /* Try to figure out what we have */ current_sbrk = (char*)(sbrk(0)); topsize = current_sbrk - (char*)top; if ((long)topsize >= (long)MINSIZE) /* if not, we are very very dead! */ { sbrked_mem = current_sbrk - sbrk_base; set_head(top, topsize | PREV_INUSE); } check_chunk(top); return 0; } else { /* Success. Adjust top accordingly. */ set_head(top, (topsize - sbrk_size) | PREV_INUSE); sbrked_mem -= sbrk_size; check_chunk(top); return 1; } } } } #if __STD_C size_t malloc_usable_size(Void_t* mem) #else size_t malloc_usable_size(mem) Void_t* mem; #endif { if (mem == 0) return 0; else { mchunkptr p = mem2chunk(mem); if (!inuse(p)) return 0; check_inuse_chunk(p); return chunksize(p) - SIZE_SZ; } } void malloc_stats() { mbinptr b; mchunkptr p; size_t malloced_mem; size_t avail = chunksize(top); for (b = &(av[1]); b < &(av[NAV]); ++b) { for (p = first(b); p != b; p = p->fd) { #if DEBUG mchunkptr q; check_free_chunk(p); for (q = next_chunk(p); q != top && inuse(q); q = next_chunk(q)) check_inuse_chunk(q); #endif avail += chunksize(p); } } malloced_mem = sbrked_mem - avail; fprintf(stderr, "maximum bytes = %10u\n", (unsigned int)max_sbrked_mem); fprintf(stderr, "current bytes = %10u\n", (unsigned int)sbrked_mem); fprintf(stderr, "in use bytes = %10u\n", (unsigned int)malloced_mem); }