doc: Add serial to list of ci file reserved words
[charm.git] / src / conv-core / memory-gnuold.c
1 #define malloc   mm_malloc
2 #define free     mm_free
3 #define calloc   mm_calloc
4 #define cfree    mm_cfree
5 #define realloc  mm_realloc
6 #define memalign mm_memalign
7 #define valloc   mm_valloc
8 #define MM_LINK static
9
10 extern CMK_TYPEDEF_UINT8 _memory_allocated;
11 extern CMK_TYPEDEF_UINT8 _memory_allocated_max;
12 extern CMK_TYPEDEF_UINT8 _memory_allocated_min;
13
14 #undef sun /* I don't care if it's a sun, dangit.  No special treatment. */
15 #undef BSD /* I don't care if it's BSD.  Same thing. */
16 #if CMK_GETPAGESIZE_AVAILABLE
17 #define HAVE_GETPAGESIZE
18 #endif
19
20
21 /* 
22   - static linkage qualifiers by Orion
23   - bugfix by Josh (fixed sbrk alignment)
24
25
26   A version of malloc/free/realloc written by Doug Lea and released to the 
27   public domain. 
28
29   VERSION 2.5.3b 
30     (Mon Jun 12 07:45:17 1995: Changed status from unreleased to 
31      released to reflect reality!)
32
33 * History:
34     Based loosely on libg++-1.2X malloc. (It retains some of the overall 
35        structure of old version,  but most details differ.)
36
37     Trial version Fri Aug 28 13:14:29 1992  Doug Lea  (dl at g.oswego.edu)
38     V2.5 Sat Aug  7 07:41:59 1993  Doug Lea  (dl at g.oswego.edu)
39       * removed potential for odd address access in prev_chunk
40       * removed dependency on getpagesize.h
41       * misc cosmetics and a bit more internal documentation
42       * anticosmetics: mangled names in macros to evade debugger strangeness
43       * tested on sparc, hp-700, dec-mips, rs6000 
44           with gcc & native cc (hp, dec only) allowing
45           Detlefs & Zorn comparison study (to appear, SIGPLAN Notices.)
46
47     V2.5.1 Sat Aug 14 15:40:43 1993  Doug Lea  (dl at g)
48       * faster bin computation & slightly different binning
49       * merged all consolidations to one part of malloc proper
50          (eliminating old malloc_find_space & malloc_clean_bin)
51       * Scan 2 returns chunks (not just 1)
52
53      Sat Apr  2 06:51:25 1994  Doug Lea  (dl at g)
54       * Propagate failure in realloc if malloc returns 0
55       * Add stuff to allow compilation on non-ANSI compilers 
56           from kpv@research.att.com
57      
58     V2.5.2 Tue Apr  5 16:20:40 1994  Doug Lea  (dl at g)
59       * realloc: try to expand in both directions
60       * malloc: swap order of clean-bin strategy;
61       * realloc: only conditionally expand backwards
62       * Try not to scavenge used bins
63       * Use bin counts as a guide to preallocation
64       * Occasionally bin return list chunks in first scan
65       * Add a few optimizations from colin@nyx10.cs.du.edu
66
67     V2.5.3 Tue Apr 26 10:16:01 1994  Doug Lea  (dl at g)
68
69 * Overview
70
71   This malloc, like any other, is a compromised design. 
72
73   Chunks of memory are maintained using a `boundary tag' method as
74   described in e.g., Knuth or Standish.  The size of the chunk is
75   stored both in the front of the chunk and at the end.  This makes
76   consolidating fragmented chunks into bigger chunks very fast.  The
77   size field also hold a bit representing whether a chunk is free or
78   in use.
79
80   Malloced chunks have space overhead of 8 bytes: The preceding and
81   trailing size fields.  When a chunk is freed, 8 additional bytes are
82   needed for free list pointers. Thus, the minimum allocatable size is
83   16 bytes.  8 byte alignment is currently hardwired into the design.
84   This seems to suffice for all current machines and C compilers.
85   Calling memalign will return a chunk that is both 8-byte aligned
86   and meets the requested (power of two) alignment.
87
88   It is assumed that 32 bits suffice to represent chunk sizes.  The
89   maximum size chunk is 2^31 - 8 bytes.  malloc(0) returns a pointer
90   to something of the minimum allocatable size.  Requests for negative
91   sizes (when size_t is signed) or with the highest bit set (when
92   unsigned) will also return a minimum-sized chunk.
93
94   Available chunks are kept in doubly linked lists. The lists are
95   maintained in an array of bins using approximately proportionally
96   spaced bins.  There are a lot of bins (128). This may look
97   excessive, but works very well in practice.  The use of very fine
98   bin sizes closely approximates the use of one bin per actually used
99   size, without necessitating the overhead of locating such bins. It
100   is especially desirable in common applications where large numbers
101   of identically-sized blocks are malloced/freed in some dynamic
102   manner, and then later are all freed.  The finer bin sizes make
103   finding blocks fast, with little wasted overallocation. The
104   consolidation methods ensure that once the collection of blocks is
105   no longer useful, fragments are gathered into bigger chunks awaiting
106   new roles.
107
108   The bins av[i] serve as heads of the lists. Bins contain a dummy
109   header for the chunk lists. Each bin has two lists. The `dirty' list
110   holds chunks that have been returned (freed) and not yet either
111   re-malloc'ed or consolidated. (A third free-standing list `returns'
112   contains returned chunks that have not yet been processed at all;
113   they must be kept with their `inuse' bits set.) The `clean' list
114   holds split-off fragments and consolidated space. All procedures
115   maintain the invariant that no clean chunk physically borders
116   another clean chunk. Thus, clean chunks never need to be scanned
117   during consolidation.  Also, dirty chunks of bad sizes (even if too
118   big) are never used without being first consolidated:
119
120   The otherwise unused size field of the bin heads are used to record
121   preallocation use. When a chunk is preallocated, an approximation of
122   the number of preallocated chunks is recorded.  Other scans try to
123   avoid `stealing' such chunks, but also decrement these counts so
124   that they age down across time.
125
126 * Algorithms
127
128   Malloc:
129
130     This is a very heavily disguised first-fit algorithm.
131     Most of the heuristics are designed to maximize the likelihood
132     that a usable chunk will most often be found very quickly,
133     while still minimizing fragmentation and overhead.
134
135     The allocation strategy has several phases. 
136
137       0. Convert the request size into a usable form. This currently
138          means to add 8 bytes overhead plus possibly more to obtain
139          8-byte alignment. Call this size `nb'.
140
141
142       1. Check if either of the last 2 returned (free()'d) or
143          preallocated chunk are of the exact size nb. If so, use one.
144          `Exact' means no more than MINSIZE (currently 16) bytes
145          larger than nb. This cannot be reduced, since a chunk with
146          size < MINSIZE cannot be created to hold the remainder.
147
148          This check need not fire very often to be effective.  It
149          reduces overhead for sequences of requests for the same
150          preallocated size to a dead minimum.  Exactly 2 peeks of the
151          return list is empirically the best tradeoff between wasting
152          time scanning unusaable chunks and the high temporal
153          correlation of chunk sizes in user programs. 
154
155
156       2. Look for a chunk in the bin associated with nb.
157
158          If a chunk was found here but not in return list, and the
159          same thing happened previously, then place the first chunk on
160          the return list in its bin. (This tends to prevent future
161          useless rescans in cases where step 3 is not hit often enough
162          because chunks are found in in bins.)
163
164       3. Pull other requests off the returned chunk list, using one if
165          it is of exact size, else distributing into the appropriate
166          (dirty) bins.
167
168       4. Look in the last scavenged bigger bin found in a previous
169          step 5, and proceed to possibly split it in step 10.
170
171       5. Scan through the clean lists of all larger bins, selecting
172          any chunk at all. (It will surely be big enough since it is
173          in a bigger bin.). The scan goes upward from small bins to
174          large to avoid fragmenting big bins we might need later.
175
176       6. Try to use a chunk remaindered during a previous malloc.
177          These chunks are kept separately in `last_remainder' to avoid
178          useless re-binning during repeated splits. Its use also tends
179          to make the scan in step 5 shorter. It must be binned prior
180          to any other consolidation.
181
182          If the chunk is usable, proceed to split, else bin it.
183
184       7. (No longer a step 7!)
185
186       8. Consolidate chunks in other dirty bins until a large enough
187          chunk is created. Break out and split when one is found.
188
189          Bins are selected for consolidation in a circular fashion
190          spanning across malloc calls. This very crudely approximates
191          LRU scanning -- it is an effective enough approximation for
192          these purposes.
193
194          After consolidating a bin, its use count decremented.
195
196     Step 9 is taken if all else fails:
197          
198       9. Get space from the system using sbrk.
199
200          Memory is gathered from the system (via sbrk) in a way that
201          allows chunks obtained across different sbrk calls to be
202          consolidated, but does not require contiguous memory. Thus,
203          it should be safe to intersperse mallocs with other sbrk
204          calls.
205
206       Step 10 can be hit from any of steps 2,4-9:
207
208       10. If the selected chunk is too big, then:
209
210          * If this is the second split request for a size in a row or
211            for a size not recently found in return lists, then use
212            this chunk to preallocate up to min {bin_use(bin)+1,
213            MAX_PREALLOCS} additional chunks of size nb and place them
214            on the returned chunk list.  (Placing them here rather than
215            in bins speeds up the most common case where the user
216            program requests an uninterrupted series of identically
217            sized chunks. If this is not true, the chunks will be
218            binned in step 4 soon.)
219
220            The actual number to prealloc depends on the available space
221            in a selected victim, so typical numbers will be less than
222            the bin_use.
223
224          * Split off the remainder and place in last_remainder
225            (first binning the old one, if applicable.)
226
227
228      10.  Return the chunk.
229
230
231   Free: 
232     Deallocation (free) consists only of placing the chunk on a list
233     of returned chunks. free(0) has no effect.  Because freed chunks
234     may be overwritten with link fields, this malloc will often die
235     when freed memory is overwritten by user programs.  This can be
236     very effective (albeit in an annoying way) in helping users track
237     down dangling pointers.
238
239   Realloc:
240     Reallocation proceeds in the usual way. If a chunk can be extended,
241     it is, else a malloc-copy-free sequence is taken. 
242
243     The old unix realloc convention of allowing the last-free'd chunk
244     to be used as an argument to realloc is half-heartedly supported.
245     It may in fact be used, but may have some old contents overwritten.
246
247   Memalign, valloc:
248     memalign arequests more than enough space from malloc, finds a spot
249     within that chunk that meets the alignment request, and then
250     possibly frees the leading and trailing space. Overreliance on
251     memalign is a sure way to fragment space.
252
253 * Other implementation notes
254
255   This malloc is NOT designed to work in multiprocessing applications.
256   No semaphores or other concurrency control are provided to ensure
257   that multiple malloc or free calls don't run at the same time, which
258   could be disasterous. A single semaphore could be used across malloc,
259   realloc, and free. It would be hard to obtain finer granularity.
260
261   The implementation is in straight, hand-tuned ANSI C.  Among other
262   consequences, it uses a lot of macros. These would be nicer as
263   inlinable procedures, but using macros allows use with non-inlining
264   compilers, and also makes it a bit easier to control when they
265   should be expanded out by selectively embedding them in other macros
266   and procedures. (According to profile information, it is almost, but
267   not quite always best to expand.) Also, because there are so many
268   different twisty paths through malloc steps, the code is not exactly
269   elegant.
270
271 */
272
273 \f
274
275 /* TUNABLE PARAMETERS */
276
277 /* 
278   SBRK_UNIT is a good power of two to call sbrk with. It should
279   normally be system page size or a multiple thereof.  If sbrk is very
280   slow on a system, it pays to increase this.  Otherwise, it should
281   not matter too much. Also, if a program needs a certain minimum
282   amount of memory, this amount can be malloc'ed then immediately
283   free'd before starting to avoid calling sbrk so often.
284 */
285
286 #define SBRK_UNIT 8192 
287
288 /* 
289   MAX_PREALLOCS is the maximum number of chunks to preallocate.  
290   Overrides bin use stats to avoid ridiculous preallocations.
291 */
292
293 #define MAX_PREALLOCS 64
294 \f
295 /* preliminaries */
296
297 #ifndef __STD_C
298 #ifdef __STDC__
299 #define __STD_C         1
300 #else
301 #if __cplusplus
302 #define __STD_C         1
303 #else
304 #define __STD_C         0
305 #endif /*__cplusplus*/
306 #endif /*__STDC__*/
307 #endif /*__STD_C*/
308
309 #ifndef _BEGIN_EXTERNS_
310 #if __cplusplus
311 #define _BEGIN_EXTERNS_ extern "C" {
312 #define _END_EXTERNS_   }
313 #else
314 #define _BEGIN_EXTERNS_
315 #define _END_EXTERNS_
316 #endif
317 #endif /*_BEGIN_EXTERNS_*/
318
319 #ifndef _ARG_
320 #if __STD_C
321 #define _ARG_(x)        x
322 #else
323 #define _ARG_(x)        ()
324 #endif
325 #endif /*_ARG_*/
326
327
328
329 #ifndef Void_t
330 #if __STD_C
331 #define Void_t          void
332 #else
333 #define Void_t          char
334 #endif
335 #endif /*Void_t*/
336
337 #ifndef NIL
338 #define NIL(type)       ((type)0)
339 #endif /*NIL*/
340
341 #if __STD_C
342 #include <stddef.h>   /* for size_t */
343 #else
344 #include <sys/types.h>
345 #endif
346
347 #include <stdio.h>    /* needed for malloc_stats */
348
349 #ifdef __cplusplus
350 extern "C" {
351 #endif
352
353 /* mechanics for getpagesize; adapted from bsd/gnu getpagesize.h */
354
355 #if defined(BSD) || defined(DGUX) || defined(sun) || defined(_WIN32) || defined(HAVE_GETPAGESIZE)
356 #  define malloc_getpagesize getpagesize()
357 #else
358 #  include <sys/param.h>
359 #  ifdef EXEC_PAGESIZE
360 #    define malloc_getpagesize EXEC_PAGESIZE
361 #  else
362 #    ifdef NBPG
363 #      ifndef CLSIZE
364 #        define malloc_getpagesize NBPG
365 #      else
366 #        define malloc_getpagesize (NBPG * CLSIZE)
367 #      endif
368 #    else 
369 #      ifdef NBPC
370 #        define malloc_getpagesize NBPC
371 #      else
372 #        define malloc_getpagesize SBRK_UNIT    /* just guess */
373 #      endif
374 #    endif 
375 #  endif
376 #endif 
377
378 #ifdef __cplusplus
379 };  /* end of extern "C" */
380 #endif
381
382
383 \f
384 /*  CHUNKS */
385
386
387 struct malloc_chunk
388 {
389   size_t size;               /* Size in bytes, including overhead. */
390                              /* Or'ed with INUSE if in use. */
391
392   struct malloc_chunk* fd;   /* double links -- used only if free. */
393   struct malloc_chunk* bk;
394
395 };
396
397 typedef struct malloc_chunk* mchunkptr;
398
399 /*  sizes, alignments */
400
401 #define SIZE_SZ              (sizeof(size_t))
402 #define MALLOC_MIN_OVERHEAD  (SIZE_SZ + SIZE_SZ)
403 #define MALLOC_ALIGN_MASK    (MALLOC_MIN_OVERHEAD - 1)
404 #define MINSIZE              (sizeof(struct malloc_chunk) + SIZE_SZ)
405
406
407 /* pad request bytes into a usable size */
408
409 #define request2size(req) \
410   (((long)(req) <= 0) ?  MINSIZE : \
411     (((req) + MALLOC_MIN_OVERHEAD + MALLOC_ALIGN_MASK) \
412       & ~(MALLOC_ALIGN_MASK)))
413
414 #define fastrequest2size(req) \
415     ((req) + MALLOC_MIN_OVERHEAD + MALLOC_ALIGN_MASK) \
416       & ~(MALLOC_ALIGN_MASK)
417
418
419 /* Check if a chunk is immediately usable */
420
421 #define exact_fit(ptr, req) ((unsigned long)((ptr)->size - (req)) < MINSIZE)
422
423 /* maintaining INUSE via size field */
424
425 #define INUSE  0x1     /* size field is or'd with INUSE when in use */
426                        /* INUSE must be exactly 1, so can coexist with size */
427
428 #define inuse(p)       ((p)->size & INUSE)
429 #define set_inuse(p)   ((p)->size |= INUSE)
430 #define clear_inuse(p) ((p)->size &= ~INUSE)
431
432 \f
433
434 /* Physical chunk operations  */
435
436 /* Ptr to next physical malloc_chunk. */
437
438 #define next_chunk(p)\
439   ((mchunkptr)( ((char*)(p)) + ((p)->size & ~INUSE) ))
440
441 /* Ptr to previous physical malloc_chunk */
442
443 #define prev_chunk(p)\
444   ((mchunkptr)( ((char*)(p)) - ( *((size_t*)((char*)(p) - SIZE_SZ)) & ~INUSE)))
445
446 /* place size at front and back of chunk */
447
448 #define set_size(P, Sz)                                                                                                           \
449 {                                                                                                                                                         \
450   size_t Sss = (Sz);                                                                                                              \
451   (P)->size = *((size_t*)((char*)(P) + Sss - SIZE_SZ)) = Sss;                             \
452 }                                                                                                                                                         \
453
454 /* set size & inuse at same time */
455 #define set_inuse_size(P, Sz)                                                                                             \
456 {                                                                                                                                                         \
457   size_t Sss = (Sz);                                                                                                              \
458   *((size_t*)((char*)(P) + Sss - SIZE_SZ)) = Sss;         \
459   (P)->size = Sss | INUSE;        \
460 }                                                                                                                                                         \
461
462
463 /* conversion from malloc headers to user pointers, and back */
464
465 #define chunk2mem(p)   ((Void_t*)((char*)(p) + SIZE_SZ))
466 #define mem2chunk(mem) ((mchunkptr)((char*)(mem) - SIZE_SZ))
467
468
469 \f
470
471 /* BINS */
472
473 struct malloc_bin
474 {
475   struct malloc_chunk dhd;   /* dirty list header */
476   struct malloc_chunk chd;   /* clean list header */
477 };
478
479 typedef struct malloc_bin* mbinptr;
480
481
482 /* field-extraction macros */
483
484 #define clean_head(b)  (&((b)->chd))
485 #define first_clean(b) ((b)->chd.fd)
486 #define last_clean(b)  ((b)->chd.bk)
487
488 #define dirty_head(b)  (&((b)->dhd))
489 #define first_dirty(b) ((b)->dhd.fd)
490 #define last_dirty(b)  ((b)->dhd.bk)
491
492 /* size field of dirty head tracks whether bin is used */
493
494 #define bin_use(b)         ((b)->dhd.size)
495 #define add_bin_use(b, nu) ((b)->dhd.size += (nu))
496 #define inc_bin_use(b)     ((b)->dhd.size++)
497 #define halve_bin_use(b)   ((b)->dhd.size=(unsigned long)((b)->dhd.size) >> 1)
498 #define clr_bin_use(b)     ((b)->dhd.size = 0)
499 #define set_bin_use(b)     ((b)->dhd.size = 1)
500
501 #define prealloc_size(b)     ((b)->chd.size)
502 #define set_prealloc_size(b, sz)  ((b)->chd.size = (sz))
503
504 \f
505
506 /* The bins, initialized to have null double linked lists */
507
508 #define NBINS     128
509 /* first 2 and last 1 bin unused but simplify indexing */
510 #define FIRSTBIN     (&(av[2]))      
511 #define LASTBIN      (&(av[NBINS-2])) 
512
513 #define PRE_FIRSTBIN (&(av[1]))      
514 #define POST_LASTBIN (&(av[NBINS-1])) 
515
516
517 /* sizes < MAX_SMALLBIN_SIZE are special-cased since bins are 8 bytes apart */
518
519 #define MAX_SMALLBIN_SIZE   512 
520 #define SMALLBIN_SIZE         8
521
522 /* Helper macro to initialize bins */
523 #define IAV(i)\
524   {{ 0, &(av[i].dhd),  &(av[i].dhd) }, { 0, &(av[i].chd),  &(av[i].chd) }}
525
526 static struct malloc_bin  av[NBINS] = 
527 {
528   IAV(0),   IAV(1),   IAV(2),   IAV(3),   IAV(4), 
529   IAV(5),   IAV(6),   IAV(7),   IAV(8),   IAV(9),
530   IAV(10),  IAV(11),  IAV(12),  IAV(13),  IAV(14), 
531   IAV(15),  IAV(16),  IAV(17),  IAV(18),  IAV(19),
532   IAV(20),  IAV(21),  IAV(22),  IAV(23),  IAV(24), 
533   IAV(25),  IAV(26),  IAV(27),  IAV(28),  IAV(29),
534   IAV(30),  IAV(31),  IAV(32),  IAV(33),  IAV(34), 
535   IAV(35),  IAV(36),  IAV(37),  IAV(38),  IAV(39),
536   IAV(40),  IAV(41),  IAV(42),  IAV(43),  IAV(44), 
537   IAV(45),  IAV(46),  IAV(47),  IAV(48),  IAV(49),
538   IAV(50),  IAV(51),  IAV(52),  IAV(53),  IAV(54), 
539   IAV(55),  IAV(56),  IAV(57),  IAV(58),  IAV(59),
540   IAV(60),  IAV(61),  IAV(62),  IAV(63),  IAV(64), 
541   IAV(65),  IAV(66),  IAV(67),  IAV(68),  IAV(69),
542   IAV(70),  IAV(71),  IAV(72),  IAV(73),  IAV(74), 
543   IAV(75),  IAV(76),  IAV(77),  IAV(78),  IAV(79),
544   IAV(80),  IAV(81),  IAV(82),  IAV(83),  IAV(84), 
545   IAV(85),  IAV(86),  IAV(87),  IAV(88),  IAV(89),
546   IAV(90),  IAV(91),  IAV(92),  IAV(93),  IAV(94), 
547   IAV(95),  IAV(96),  IAV(97),  IAV(98),  IAV(99),
548   IAV(100), IAV(101), IAV(102), IAV(103), IAV(104), 
549   IAV(105), IAV(106), IAV(107), IAV(108), IAV(109),
550   IAV(110), IAV(111), IAV(112), IAV(113), IAV(114), 
551   IAV(115), IAV(116), IAV(117), IAV(118), IAV(119),
552   IAV(120), IAV(121), IAV(122), IAV(123), IAV(124), 
553   IAV(125), IAV(126), IAV(127)
554 };
555
556 \f
557
558 /* 
559   Auxiliary globals 
560
561   Returns hold list of (unbinned) returned chunks
562
563   Even though it uses bk/fd ptrs, returns is NOT doubly linked!
564   It is singly-linked and null-terminated it is only they are
565   accessed sequentially.
566
567 */
568
569 static mchunkptr returns = 0;  
570
571 /* 
572   last_remainder holds for the remainder of the most recently split chunk
573 */
574
575
576 static mchunkptr last_remainder = 0; 
577
578
579
580 /* 
581   minClean and maxClean keep track of the minimum/maximum actually used 
582   clean bin, to make loops faster 
583 */
584
585 static mbinptr maxClean = PRE_FIRSTBIN;
586 static mbinptr minClean = POST_LASTBIN;
587
588
589 \f
590
591 /* 
592   Indexing into bins 
593
594   Bins are log-spaced:
595
596   64 bins of size       8
597   32 bins of size      64
598   16 bins of size     512
599    8 bins of size    4096
600    4 bins of size   32768
601    2 bins of size  262144
602    1 bin  of size what's left
603
604   There is actually a little bit of slop in the numbers in findbin()
605   for the sake of speed. This makes no difference elsewhere.
606 */
607
608 #define findbin(Sizefb, Bfb)                                                                                              \
609 {                                                                                                                                                         \
610   unsigned long  Ofb = (Sizefb) >> 3;                                                                             \
611   unsigned long  Nfb = Ofb >> 6;                                                                                          \
612   if (Nfb != 0)  {                                                                                                                        \
613     if      (Nfb <    5)  Ofb = (Ofb >>  3) +  56;                                                        \
614     else if (Nfb <   21)  Ofb = (Ofb >>  6) +  91;                                                \
615     else if (Nfb <   85)  Ofb = (Ofb >>  9) + 110;                                                \
616     else if (Nfb <  341)  Ofb = (Ofb >> 12) + 119;                                                \
617     else if (Nfb < 1365)  Ofb = (Ofb >> 15) + 124;                                                \
618     else                  Ofb = 126;                                                                              \
619   }                                                                                                                                                       \
620   (Bfb) = av + Ofb;                                                                                                                       \
621 }                                                                                                                                                         \
622
623 /* Special case for known small bins */
624
625 #define smallfindbin(Sizefb, Bfb) (Bfb) = av + ((unsigned long)(Sizefb) >> 3)
626
627
628
629 \f
630
631
632
633 /* Macros for linking and unlinking chunks */
634
635 /* take a chunk off a list */
636
637 #define unlink(Qul)                                                                                                                       \
638 {                                                                                                                                                         \
639   mchunkptr Bul = (Qul)->bk;                                                                                              \
640   mchunkptr Ful = (Qul)->fd;                                                                                              \
641   Ful->bk = Bul;  Bul->fd = Ful;                                                                                          \
642 }                                                                                                                                                         \
643
644
645 /* place a chunk on the dirty list of its bin */
646
647 #define dirtylink(Qdl)                                                                                                            \
648 {                                                                                                                                                         \
649   mchunkptr Pdl = (Qdl);                                                                                                          \
650   mbinptr   Bndl;                                                                                                                         \
651   mchunkptr Hdl, Fdl;                                                                                                             \
652   clear_inuse(Pdl);                                                                                                                       \
653   findbin(Pdl->size, Bndl);                                                                                                       \
654   Hdl  = dirty_head(Bndl);                                                                                                        \
655   Fdl  = Hdl->fd;                                                                                                                         \
656   Pdl->bk = Hdl;  Pdl->fd = Fdl;  Fdl->bk = Hdl->fd = Pdl;                                        \
657 }                                                                                                                                                         \
658
659
660 /* Place a consolidated chunk on a clean list */
661
662 #define cleanlink(Qcl)                                                                                                            \
663 {                                                                                                                                                         \
664   mchunkptr Pcl = (Qcl);                                                                                                          \
665   mbinptr Bcl;                                                                                                                            \
666   mchunkptr Hcl, Fcl;                                                                                                             \
667                                                                                                                                                           \
668   findbin(Qcl->size, Bcl);                                                                                                        \
669   Hcl  = clean_head(Bcl);                                                                                                         \
670   Fcl  = Hcl->fd;                                                                                                                         \
671   if (Hcl == Fcl) {                                                           \
672     if (Bcl < minClean) minClean = Bcl;                                       \
673     if (Bcl > maxClean) maxClean = Bcl;                                       \
674   }                                                                                                       \
675   Pcl->bk = Hcl;  Pcl->fd = Fcl;  Fcl->bk = Hcl->fd = Pcl;                                        \
676 }                                                                                                                                                         \
677
678
679 #if __STD_C
680 static void callcleanlink(mchunkptr p) 
681 #else
682 static void callcleanlink(p) mchunkptr p;
683 #endif
684
685   cleanlink(p); 
686 }
687
688
689
690 /* consolidate one chunk */
691
692 #define consolidate(Qc)                                                                                                           \
693 {                                                                                                                                                         \
694   for (;;)                                                                                                                                        \
695   {                                                                                                                                                       \
696     mchunkptr Pc = prev_chunk(Qc);                                                                                        \
697     if (!inuse(Pc))                                                                                                                       \
698     {                                                                                                                                             \
699       unlink(Pc);                                                                                                                         \
700       set_size(Pc, Pc->size + (Qc)->size);                                                                        \
701       (Qc) = Pc;                                                                                                                          \
702     }                                                                                                                                             \
703     else break;                                                                                                                           \
704   }                                                                                                                                                       \
705   for (;;)                                                                                                                                        \
706   {                                                                                                                                                       \
707     mchunkptr Nc = next_chunk(Qc);                                                                                        \
708     if (!inuse(Nc))                                                                                                                       \
709     {                                                                                                                                             \
710       unlink(Nc);                                                                                                                         \
711       set_size((Qc), (Qc)->size + Nc->size);                                                              \
712     }                                                                                                                                             \
713     else break;                                                                                                                           \
714   }                                                                                                                                                       \
715 }                                                                                                                                                         \
716
717
718 /* Place a freed chunk on the returns */
719
720 #define returnlink(Prc)                                                                                                   \
721 {                                                                                                                                                         \
722   (Prc)->fd = returns;                                                                                            \
723   returns = (Prc);                                                                                                        \
724 }                                                                                                                                                         \
725
726
727 \f
728 /* Misc utilities */
729
730 /* A helper for realloc */
731
732 static void clear_aux_lists()
733 {
734   if (last_remainder != 0)
735   {                             
736     cleanlink(last_remainder);
737     last_remainder = 0;
738   }                                                             
739
740   while (returns != 0)
741   {
742     mchunkptr p = returns;
743     returns = p->fd;
744     dirtylink(p);
745   }
746 }
747
748
749 \f
750
751 /* Dealing with sbrk */
752 /* This is one step of malloc; broken out for simplicity */
753
754 static size_t sbrked_mem = 0; /* Keep track of total mem for malloc_stats */
755
756 #if __STD_C
757 static mchunkptr malloc_from_sys(size_t nb)
758 #else
759 static mchunkptr malloc_from_sys(nb) size_t nb;
760 #endif
761 {
762
763   /* The end of memory returned from previous sbrk call */
764   static size_t* last_sbrk_end = 0; 
765
766   mchunkptr p;            /* Will hold a usable chunk */
767   size_t*   ip;           /* to traverse sbrk ptr in size_t units */
768   char*     cp;           /* result of sbrk call */
769   int       offs;         /* bytes must add for alignment */
770   
771   /* Find a good size to ask sbrk for.  */
772   /* Minimally, we need to pad with enough space */
773   /* to place dummy size/use fields to ends if needed */
774
775   size_t sbrk_size = ((nb + SBRK_UNIT - 1 + SIZE_SZ + SIZE_SZ) 
776                        / SBRK_UNIT) * SBRK_UNIT;
777
778   cp = (char*)(sbrk(sbrk_size));
779   if (cp == (char*)(-1)) /* sbrk returns -1 on failure */
780     return 0;
781   sbrked_mem += sbrk_size;
782
783   if (((size_t)cp) & MALLOC_ALIGN_MASK) {
784     offs = ((size_t)cp) & MALLOC_ALIGN_MASK;
785     cp += MALLOC_MIN_OVERHEAD - offs;
786     sbrk_size -= MALLOC_MIN_OVERHEAD;
787     sbrk(- offs);
788   }
789     
790   ip = (size_t*)cp;
791
792   if (last_sbrk_end != &ip[-1]) /* Is this chunk continguous with last? */
793   {                             
794     /* It's either first time through or someone else called sbrk. */
795     /* Arrange end-markers at front & back */
796
797     /* Mark the front as in use to prevent merging. (End done below.) */
798     /* Note we can get away with only 1 word, not MINSIZE overhead here */
799
800     *ip++ = SIZE_SZ | INUSE;
801     
802     p = (mchunkptr)ip;
803     set_size(p,sbrk_size - (SIZE_SZ + SIZE_SZ)); 
804     
805   }
806   else 
807   {
808     mchunkptr l;  
809
810     /* We can safely make the header start at end of prev sbrked chunk. */
811     /* We will still have space left at the end from a previous call */
812     /* to place the end marker, below */
813
814     p = (mchunkptr)(last_sbrk_end);
815     set_size(p, sbrk_size);
816
817     /* Even better, maybe we can merge with last fragment: */
818
819     l = prev_chunk(p);
820     if (!inuse(l))  
821     {
822       unlink(l);
823       set_size(l, p->size + l->size);
824       p = l;
825     }
826
827   }
828
829   /* mark the end of sbrked space as in use to prevent merging */
830
831   last_sbrk_end = (size_t*)((char*)p + p->size);
832   *last_sbrk_end = SIZE_SZ | INUSE;
833
834   return p;
835 }
836
837 \f
838
839 /* The less-frequent steps of malloc broken out as a procedure. */
840 /* (Allows compilers to better optimize main steps.) */
841  
842 #if __STD_C
843 static mchunkptr malloc_consolidate(size_t nb)
844 #else
845 static mchunkptr malloc_consolidate(nb) size_t nb;
846 #endif
847 {
848   static mbinptr rover = LASTBIN;        /* Circular ptr for consolidation */
849
850   mbinptr origin, b;
851
852   /* Consolidate last remainder first. */
853   /* It must be binned before any other consolidations, so might as well */
854   /* consolidate it too.  This also helps make up for false-alarm  */
855   /* preallocations */
856
857   mchunkptr victim = last_remainder;
858   last_remainder = 0;
859
860   if (victim != 0)
861   {
862     consolidate(victim);
863     
864     if (victim->size >= nb)
865       return victim;
866     else
867       cleanlink(victim);
868   }
869
870   /* -------------- Sweep through and consolidate other dirty bins */
871
872   origin = rover;     /* Start where left off last time. */
873   b      = rover;
874   do
875   {
876     halve_bin_use(b);  /* decr use counts while traversing */
877     
878     while ( (victim = last_dirty(b)) != dirty_head(b))
879     {
880       unlink(victim);
881       consolidate(victim);
882       
883       if (victim->size >= nb)
884       {
885         rover = b;
886         return victim;
887       }
888       else
889         cleanlink(victim);
890     }
891     
892     
893     b = (b <= FIRSTBIN)? LASTBIN : b - 1;      /* circularly sweep */
894     
895   } while (b != origin);
896
897   
898   /* -------------  Nothing available; get some from sys */
899
900   return malloc_from_sys(nb);
901 }
902
903
904 #if __STD_C
905 MM_LINK Void_t* malloc(size_t bytes)
906 #else
907 MM_LINK Void_t* malloc(bytes) size_t bytes;
908 #endif
909 {
910   static mchunkptr bad_rl_chunk = 0;     /* last scanned return-list chunk */
911   static mbinptr prevClean = FIRSTBIN;  /* likely clean bin to use */
912
913   mchunkptr victim;                      /* will hold selected chunk */
914   mbinptr   bin;                         /* corresponding bin */
915
916   /* ----------- Peek (twice) at returns; hope for luck */
917
918   mchunkptr rl = returns;                /* local for speed/simplicity */
919   size_t nb = request2size(bytes)    ;   /* padded request size; */
920
921   _memory_allocated += nb;
922
923   if(_memory_allocated > _memory_allocated_max)
924     _memory_allocated_max=_memory_allocated;
925   if(_memory_allocated < _memory_allocated_min)
926     _memory_allocated_min=_memory_allocated;
927
928   if (rl != 0)
929   {
930     mchunkptr snd = rl->fd;
931     if (exact_fit(rl, nb)) /* size check works even though INUSE set */
932     {
933       returns = snd;
934       return chunk2mem(rl);
935     }
936     else if (snd != 0 && exact_fit(snd, nb))
937     {
938       returns->fd = snd->fd;
939       return chunk2mem(snd);
940     }
941     else if (rl == bad_rl_chunk)     /* If we keep failing, bin one */
942     {
943       dirtylink(rl);
944       returns = rl = snd;
945     }
946     bad_rl_chunk = rl;
947   }
948
949
950
951   /* ---------- Scan own dirty bin */
952
953   if (nb < (MAX_SMALLBIN_SIZE - SMALLBIN_SIZE))
954   {
955     /* Small bins special-cased since no size check or traversal needed. */
956     /* Also because of MINSIZE slop, next dirty bin is exact fit too */
957
958     smallfindbin(nb, bin);
959
960     if ( ((victim = last_dirty(bin)) != dirty_head(bin)) ||
961          ((victim = last_clean(bin)) != clean_head(bin)) ||
962          ((victim = last_dirty(bin+1)) != dirty_head(bin+1)))
963     {
964       unlink(victim);
965       set_inuse(victim);
966       return chunk2mem(victim);
967     }
968
969   }
970   else
971   {
972     findbin(nb, bin);
973
974     for (victim=last_dirty(bin); victim != dirty_head(bin); victim=victim->bk)
975     {
976       if (exact_fit(victim, nb))     /* Can use exact matches only here */
977       {
978         unlink(victim);
979         set_inuse(victim);
980         return chunk2mem(victim);
981       }
982     }
983
984     for (victim=last_clean(bin); victim != clean_head(bin); victim=victim->bk)
985     {
986       if (victim->size >= nb)
987       {
988         unlink(victim); 
989         goto split;
990       }
991     }
992   }
993
994
995   /* ------------ Search return list, placing unusable chunks in their bins  */
996
997
998   if (rl != 0)
999   {
1000     victim = rl;  
1001     rl = rl->fd;
1002     for (;;)
1003     {
1004       dirtylink(victim);
1005       if (rl == 0)
1006       {
1007         returns = rl;
1008         break;
1009       }
1010       victim = rl;
1011       rl = rl->fd;
1012       if (exact_fit(victim, nb))
1013       {
1014         bad_rl_chunk = returns = rl;
1015         return chunk2mem(victim);
1016       }
1017     }
1018   }
1019
1020   if (bin < maxClean)
1021   {
1022     mbinptr b;
1023
1024     /* -------------- First try last successful clean bin  */
1025
1026     if (bin < prevClean) 
1027     {
1028       if ( (victim = last_clean(prevClean)) != clean_head(prevClean) ) 
1029       {
1030         unlink(victim);
1031         goto split;
1032       }
1033     }
1034
1035
1036     /* -------------- Scan others  */
1037
1038     for (b = (bin < minClean)? minClean : (bin + 1); b <= maxClean; ++b)
1039     {
1040       if ( (victim = last_clean(b)) != clean_head(b) ) 
1041       {
1042         /* If more, record  */
1043         if (bin_use(b) == 0 && victim->bk != clean_head(b)) prevClean = b;
1044         else { halve_bin_use(b); prevClean = FIRSTBIN; }
1045
1046         unlink(victim);
1047         if (bin < minClean) minClean = b;         /* b must be <= true min */
1048         goto split;
1049       }
1050     }
1051
1052     /* --------------  If fall through, recompute bounds for next time */
1053
1054     while (maxClean >= FIRSTBIN && clean_head(maxClean)==last_clean(maxClean))
1055       --maxClean;
1056     if (maxClean < FIRSTBIN) /* reset at endpoints if no clean bins */
1057       minClean = POST_LASTBIN;
1058     else
1059     {
1060       while (minClean < maxClean && clean_head(minClean)==last_clean(minClean))
1061         ++minClean;
1062     }
1063
1064     prevClean = FIRSTBIN;
1065
1066   }
1067
1068
1069   /* -------------- Try remainder from previous split */
1070     
1071   if ( (victim = last_remainder) != 0)
1072   {
1073     if (victim->size >= nb)
1074     {
1075       last_remainder = 0;
1076       goto split;
1077     }
1078   }
1079
1080
1081   /* -------------- Other steps called via malloc_consolidate */
1082
1083   victim = malloc_consolidate(nb);
1084   if (victim == 0) return 0;   /* propagate failure */
1085
1086
1087   /* -------------- Possibly split victim chunk */
1088
1089  split:  
1090   {
1091     size_t room = victim->size - nb;
1092
1093     if (room < MINSIZE)
1094     {
1095       set_inuse(victim);
1096       return chunk2mem(victim);
1097     }
1098     else    /* must create remainder */ 
1099     {
1100       mchunkptr remainder;
1101       int desired;
1102
1103       set_inuse_size(victim, nb);
1104       remainder = (mchunkptr)((char*)(victim) + nb);
1105
1106       desired = inc_bin_use(bin);
1107
1108       /* ---------- Preallocate more of this size */
1109
1110       if (nb < MAX_SMALLBIN_SIZE && room >= nb + MINSIZE && desired != 0) 
1111       {
1112         int actual = 1;
1113
1114         /* place in ascending order on ret list */
1115         mchunkptr first = remainder;
1116         mchunkptr last = remainder;
1117         set_inuse_size(remainder, nb);
1118         remainder = (mchunkptr)((char*)(remainder) + nb);
1119         
1120         if (desired > MAX_PREALLOCS)  desired = MAX_PREALLOCS;
1121         
1122         while ( (room -= nb) >= nb + MINSIZE && actual < desired)
1123         {
1124           ++actual;
1125           set_inuse_size(remainder, nb);
1126           last->fd = remainder; 
1127           last = remainder; 
1128           remainder = (mchunkptr)((char*)(remainder) + nb);
1129         }
1130         
1131         last->fd = returns;
1132         returns = first;
1133         
1134         add_bin_use(bin, actual); 
1135       }
1136
1137       /* ---------- Put away remainder chunk  */
1138
1139       set_size(remainder, room);
1140
1141       /* get rid of old one */
1142       if (last_remainder != 0) callcleanlink(last_remainder);
1143       last_remainder = remainder;
1144
1145       return chunk2mem(victim);
1146
1147     }
1148   }
1149 }
1150
1151
1152 \f
1153
1154 #if __STD_C
1155 MM_LINK void free(Void_t* mem)
1156 #else
1157 MM_LINK void free(mem) Void_t* mem;
1158 #endif
1159 {
1160   if (mem != 0)
1161   {
1162     mchunkptr p = mem2chunk(mem);
1163     _memory_allocated -= p->size;
1164     returnlink(p);
1165   }
1166 }
1167
1168  
1169 \f
1170
1171 /* Special-purpose copy for realloc */
1172 /* Copy bytes in size_t units, adjusting for chunk header */
1173
1174 #define SCopy(SCs,SCd,SCc)                                                                                                        \
1175 {                                                                                                                                                         \
1176   size_t * SCsrc = (size_t*) SCs;                                                                                         \
1177   size_t * SCdst = (size_t*) SCd;                                                                                         \
1178   size_t SCcount = (SCc - SIZE_SZ) / sizeof(size_t);                                              \
1179   do { *SCdst++ = *SCsrc++; } while (--SCcount > 0);                                              \
1180 }
1181
1182
1183 #if __STD_C
1184 MM_LINK Void_t* realloc(Void_t* mem, size_t bytes)
1185 #else
1186 MM_LINK Void_t* realloc(mem, bytes) Void_t* mem; size_t bytes;
1187 #endif
1188 {
1189   if (mem == 0) 
1190     return malloc(bytes);
1191   else
1192   {
1193     size_t       nb      = request2size(bytes);
1194     mchunkptr    p       = mem2chunk(mem);
1195     size_t       oldsize;
1196     Void_t*      newmem;
1197     size_t       room;
1198     int          back_expanded = 0;
1199
1200     if (p == returns) /* sorta support realloc-last-freed-chunk idiocy */
1201        returns = returns->fd;
1202
1203     clear_inuse(p);
1204     oldsize = p->size;
1205
1206     /* try to expand. */
1207
1208     clear_aux_lists();     /* make freed chunks available to consolidate */
1209
1210     if (p->size < nb)      /* forward as far as possible */
1211     {
1212       for (;;)
1213       {
1214         mchunkptr nxt = next_chunk(p);
1215         if (!inuse(nxt))
1216         {
1217           unlink(nxt);
1218           set_size(p, p->size + nxt->size);
1219         }
1220         else break;
1221       }
1222     }
1223
1224     while (p->size < nb)  /* backward only if and as far as necessary */
1225     {
1226       mchunkptr prv = prev_chunk(p);
1227       if (!inuse(prv))                                  
1228       {
1229         back_expanded = 1;
1230         unlink(prv);
1231         set_size(prv, prv->size + p->size);
1232         p = prv;
1233       }
1234       else break;
1235     }
1236
1237     if (p->size < nb)    /* Could not expand. Get another chunk. */
1238     {
1239       mchunkptr    newp;
1240
1241       set_inuse(p);      /* don't let malloc consolidate p yet! */
1242       newmem = malloc(nb);
1243       newp = mem2chunk(newmem); 
1244
1245       /* Avoid copy if newp is next chunk after oldp. */
1246       /* This can only happen when new chunk is sbrk'ed, */
1247       /* which is common enough in reallocs to deal with here. */
1248
1249       if (newp == next_chunk(p)) 
1250       {
1251
1252         if (back_expanded) /* Must copy first anyway; still worth it */
1253           SCopy(mem, chunk2mem(p), oldsize);
1254
1255         clear_inuse(p);
1256         clear_inuse(newp);
1257         set_size(p, p->size + newp->size);
1258
1259         room = p->size - nb;
1260         if (room >= MINSIZE)  /* give some back */
1261         {
1262           mchunkptr remainder = (mchunkptr)((char*)(p) + nb);
1263           set_size(remainder, room);
1264           set_size(p, nb);
1265
1266           /* clean up remainder; it must be start of new sbrked space */
1267           clear_aux_lists();   /* Clear, in case malloc preallocated */
1268           for (;;)
1269           {
1270             mchunkptr nxt = next_chunk(remainder);
1271             if (!inuse(nxt))
1272             {
1273               unlink(nxt);
1274               set_size(remainder, remainder->size + nxt->size);
1275             }
1276             else break;
1277           }
1278           last_remainder = remainder;
1279         }
1280
1281         set_inuse(p);
1282         return chunk2mem(p);
1283       }
1284       else
1285       {
1286         if (newmem != 0) SCopy(mem, newmem, oldsize);
1287         returnlink(p);
1288         return newmem;
1289       }
1290     }
1291     else
1292     {
1293       room = p->size - nb;
1294       newmem = chunk2mem(p);
1295
1296       if (back_expanded) SCopy(mem, newmem, oldsize);
1297         
1298       if (room >= MINSIZE)  /* give some back if possible */
1299       {
1300         mchunkptr remainder = (mchunkptr)((char*)(p) + nb);
1301         set_size(remainder, room);
1302         dirtylink(remainder); /* not sure; be safe */
1303         set_size(p, nb);
1304       }
1305
1306       set_inuse(p);
1307       return chunk2mem(p);
1308     }
1309   }
1310 }
1311
1312 \f
1313
1314 /* Return a pointer to space with at least the alignment requested */
1315 /* Alignment argument should be a power of two */
1316
1317 #if __STD_C
1318 MM_LINK Void_t* memalign(size_t alignment, size_t bytes)
1319 #else
1320 MM_LINK Void_t* memalign(alignment, bytes) size_t alignment; size_t bytes;
1321 #endif
1322 {
1323   mchunkptr p;
1324   size_t    nb = request2size(bytes);
1325   size_t    room;
1326
1327   /* find an alignment that both we and the user can live with: */
1328
1329   size_t    align = (alignment > MALLOC_MIN_OVERHEAD) ? 
1330                      alignment : MALLOC_MIN_OVERHEAD;
1331
1332   /* call malloc with worst case padding to hit alignment; */
1333   /* we will give back extra */
1334
1335   size_t req = nb + align + MINSIZE;
1336   Void_t*  m = malloc(req);
1337
1338   if (m == 0) return 0; /* propagate failure */
1339
1340   p = mem2chunk(m);
1341   clear_inuse(p);
1342
1343
1344   if (((size_t)(m) % align) != 0) /* misaligned */
1345   {
1346
1347     /* find an aligned spot inside chunk */
1348
1349     mchunkptr ap = (mchunkptr)((((size_t)(m) + align-1) & -align) - SIZE_SZ);
1350
1351     size_t gap = (size_t)(ap) - (size_t)(p);
1352
1353     /* we need to give back leading space in a chunk of at least MINSIZE */
1354
1355     if (gap < MINSIZE)
1356     {
1357       /* This works since align >= MINSIZE */
1358       /* and we've malloc'd enough total room */
1359
1360       ap = (mchunkptr)( (size_t)(ap) + align );
1361       gap += align;    
1362     }
1363
1364     room = p->size - gap;
1365
1366     /* give back leader */
1367     set_size(p, gap);
1368     dirtylink(p);
1369
1370     /* use the rest */
1371     p = ap;
1372     set_size(p, room);
1373   }
1374
1375   /* also give back spare room at the end */
1376
1377   room = p->size - nb;
1378   if (room >= MINSIZE)
1379   {
1380     mchunkptr remainder = (mchunkptr)((char*)(p) + nb);
1381     set_size(remainder, room);
1382     dirtylink(remainder);
1383     set_size(p, nb);
1384   }
1385
1386   set_inuse(p);
1387   return chunk2mem(p);
1388
1389 }
1390
1391 \f
1392
1393 /* Derivatives */
1394
1395 #if __STD_C
1396 MM_LINK Void_t* valloc(size_t bytes)
1397 #else
1398 MM_LINK Void_t* valloc(bytes) size_t bytes;
1399 #endif
1400 {
1401   /* Cache result of getpagesize */
1402   static size_t malloc_pagesize = 0;
1403
1404   if (malloc_pagesize == 0) malloc_pagesize = malloc_getpagesize;
1405   return memalign (malloc_pagesize, bytes);
1406 }
1407
1408
1409 #if __STD_C
1410 MM_LINK Void_t* calloc(size_t n, size_t elem_size)
1411 #else
1412 MM_LINK Void_t* calloc(n, elem_size) size_t n; size_t elem_size;
1413 #endif
1414 {
1415   size_t sz = n * elem_size;
1416   Void_t* p = malloc(sz);
1417   char* q = (char*) p;
1418   while (sz-- > 0) *q++ = 0;
1419   return p;
1420 }
1421
1422 #if __STD_C
1423 MM_LINK void cfree(Void_t *mem)
1424 #else
1425 MM_LINK void cfree(mem) Void_t *mem;
1426 #endif
1427 {
1428   free(mem);
1429 }
1430
1431 #if __STD_C
1432 size_t malloc_usable_size(Void_t* mem)
1433 #else
1434 size_t malloc_usable_size(mem) Void_t* mem;
1435 #endif
1436 {
1437   if (mem == 0)
1438     return 0;
1439   else
1440   {
1441     mchunkptr p = mem2chunk(mem);
1442     size_t sz = p->size & ~(INUSE);
1443     /* report zero if not in use or detectably corrupt */
1444     if (p->size == sz || sz != *((size_t*)((char*)(p) + sz - SIZE_SZ)))
1445       return 0;
1446     else
1447       return sz - MALLOC_MIN_OVERHEAD;
1448   }
1449 }
1450     
1451 \f
1452 void malloc_stats()
1453 {
1454
1455   /* Traverse through and count all sizes of all chunks */
1456
1457   size_t avail = 0;
1458   size_t malloced_mem;
1459
1460   mbinptr b;
1461
1462   clear_aux_lists();
1463
1464   for (b = FIRSTBIN; b <= LASTBIN; ++b)
1465   {
1466     mchunkptr p;
1467
1468     for (p = first_dirty(b); p != dirty_head(b); p = p->fd)
1469       avail += p->size;
1470
1471     for (p = first_clean(b); p != clean_head(b); p = p->fd)
1472       avail += p->size;
1473   }
1474
1475   malloced_mem = sbrked_mem - avail;
1476
1477   fprintf(stderr, "total mem = %10u\n", (unsigned int)sbrked_mem);
1478   fprintf(stderr, "in use    = %10u\n", (unsigned int)malloced_mem);
1479
1480 }
1481
1482 #undef malloc
1483 #undef free
1484 #undef calloc
1485 #undef cfree
1486 #undef realloc
1487 #undef memalign
1488 #undef valloc
1489