4 Copyright (C) 1989 Free Software Foundation
5 written by Doug Lea (dl@oswego.edu)
7 This file is part of GNU CC.
9 GNU CC is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY. No author or distributor
11 accepts responsibility to anyone for the consequences of using it
12 or for whether it serves any particular purpose or works at all,
13 unless he says so in writing. Refer to the GNU CC General Public
14 License for full details.
16 Everyone is granted permission to copy, modify and redistribute
17 GNU CC, but only under the conditions described in the
18 GNU CC General Public License. A copy of this license is
19 supposed to have been given to you along with GNU CC so you
20 can know your rights and responsibilities. It should be in a
21 file named COPYING. Among other things, the copyright notice
22 and this notice must be preserved on all copies.
27 #ifndef NO_LIBGXX_MALLOC /* ignore whole file otherwise */
29 /* compile with -DMALLOC_STATS to collect statistics */
30 /* collecting statistics slows down malloc by at least 15% */
33 #define UPDATE_STATS(ARGS) {ARGS;}
35 #define UPDATE_STATS(ARGS)
41 Tue Jan 16 04:54:27 1990 Doug Lea (dl at g.oswego.edu)
43 version 1 released in libg++
45 Sun Jan 21 05:52:47 1990 Doug Lea (dl at g.oswego.edu)
47 bins are now own struct for, sanity.
49 new victim search strategy: scan up and consolidate.
50 Both faster and less fragmentation.
52 refined when to scan bins for consolidation, via consollink, etc.
54 realloc: always try to expand chunk, avoiding some fragmentation.
56 changed a few inlines into macros
58 hardwired SBRK_UNIT to 4096 for uniformity across systems
60 Tue Mar 20 14:18:23 1990 Doug Lea (dl at g.oswego.edu)
62 calloc and cfree now correctly parameterized.
64 Sun Apr 1 10:00:48 1990 Doug Lea (dl at g.oswego.edu)
66 added memalign and valloc.
68 Sun Jun 24 05:46:48 1990 Doug Lea (dl at g.oswego.edu)
70 #include gepagesize.h only ifndef sun
71 cache pagesize after first call
73 Wed Jul 25 08:35:19 1990 Doug Lea (dl at g.oswego.edu)
75 No longer rely on a `designated victim':
77 1. It sometimes caused splits of large chunks
78 when smaller ones would do, leading to
79 bad worst-case fragmentation.
81 2. Scanning through the av array fast anyway,
82 so the overhead isn't worth it.
84 To compensate, several other minor changes:
86 1. Unusable chunks are checked for consolidation during
87 searches inside bins, better distributing chunks
90 2. Chunks are returned when found in malloc_find_space,
91 rather than finishing cleaning everything up, to
92 avoid wasted iterations due to (1).
96 A version of malloc/free/realloc tuned for C++ applications.
98 Here's what you probably want to know first:
100 In various tests, this appears to be about as fast as,
101 and usually substantially less memory-wasteful than BSD/GNUemacs malloc.
103 Generally, it is slower (by perhaps 20%) than bsd-style malloc
104 only when bsd malloc would waste a great deal of space in
105 fragmented blocks, which this malloc recovers; or when, by
106 chance or design, nearly all requests are near the bsd malloc
107 power-of-2 allocation bin boundaries, and as many chunks are
108 used as are allocated.
110 It uses more space than bsd malloc only when, again by chance
111 or design, only bsdmalloc bin-sized requests are malloced, or when
112 little dynamic space is malloced, since this malloc may grab larger
113 chunks from the system at a time than bsd.
115 In other words, this malloc seems generally superior to bsd
116 except perhaps for programs that are specially tuned to
117 deal with bsdmalloc's characteristics. But even here, the
118 performance differences are slight.
121 This malloc, like any other, is a compromised design.
124 Chunks of memory are maintained using a `boundary tag' method as
125 described in e.g., Knuth or Standish. This means that the size of
126 the chunk is stored both in the front of the chunk and at the end.
127 This makes consolidating fragmented chunks into bigger chunks very fast.
128 The size field is also used to hold bits representing whether a
129 chunk is free or in use.
131 Malloced chunks have space overhead of 8 bytes: The preceding
132 and trailing size fields. When they are freed, the list pointer
133 fields are also needed.
135 Available chunks are kept in doubly linked lists. The lists are
136 maintained in an array of bins using a power-of-two method, except
137 that instead of 32 bins (one for each 1 << i), there are 128: each
138 power of two is split in quarters. The use of very fine bin sizes
139 closely approximates the use of one bin per actually used size,
140 without necessitating the overhead of locating such bins. It is
141 especially desirable in common C++ applications where large numbers
142 of identically-sized blocks are malloced/freed in some dynamic
143 manner, and then later are all freed. The finer bin sizes make
144 finding blocks fast, with little wasted overallocation. The
145 consolidation methods ensure that once the collection of blocks is
146 no longer useful, fragments are gathered into bigger chunks awaiting new
149 The bins av[i] serve as heads of the lists. Bins contain a dummy
150 header for the chunk lists, and a `dirty' field used to indicate
151 whether the list may need to be scanned for consolidation.
153 On allocation, the bin corresponding to the request size is
154 scanned, and if there is a chunk with size >= requested, it
155 is split, if too big, and used. Chunks on the list which are
156 too small are examined for consolidation during this traversal.
158 If no chunk exists in the list bigger bins are scanned in search of
161 If no victim can be found, then smaller bins are examined for
162 consolidation in order to construct a victim.
164 Finally, if consolidation fails to come up with a usable chunk,
165 more space is obtained from the system.
167 After a split, the remainder is placed on
168 the back of the appropriate bin list. (All freed chunks are placed
169 on fronts of lists. All remaindered or consolidated chunks are
170 placed on the rear. Correspondingly, searching within a bin
171 starts at the front, but finding victims is from the back. All
172 of this approximates the effect of having 2 kinds of lists per
173 bin: returned chunks vs unallocated chunks, but without the overhead
174 of maintaining 2 lists.)
176 Deallocation (free) consists only of placing the chunk on
179 Reallocation proceeds in the usual way. If a chunk can be extended,
180 it is, else a malloc-copy-free sequence is taken.
182 memalign requests more than enough space from malloc, finds a
183 spot within that chunk that meets the alignment request, and
184 then possibly frees the leading and trailing space. Overreliance
185 on memalign is a sure way to fragment space.
188 Some other implementation matters:
190 8 byte alignment is currently hardwired into the design. Calling
191 memalign will return a chunk that is both 8-byte aligned, and
192 meets the requested alignment.
194 The basic overhead of a used chunk is 8 bytes: 4 at the front and
197 When a chunk is free, 8 additional bytes are needed for free list
198 pointers. Thus, the minimum allocatable size is 16 bytes.
200 The existence of front and back overhead permits some reasonably
201 effective fence-bashing checks: The front and back fields must
202 be identical. This is checked only within free() and realloc().
203 The checks are fast enough to be made non-optional.
205 The overwriting of parts of freed memory with the freelist pointers
206 can also be very effective (albeit in an annoying way) in helping
207 users track down dangling pointers.
209 User overwriting of freed space will often result in crashes
210 within malloc or free.
212 These routines are also tuned to C++ in that free(0) is a noop and
213 a failed malloc automatically calls (*new_handler)().
215 malloc(0) returns a pointer to something of the minimum allocatable size.
217 Additional memory is gathered from the system (via sbrk) in a
218 way that allows chunks obtained across different sbrk calls to
219 be consolidated, but does not require contiguous memory: Thus,
220 it should be safe to intersperse mallocs with other sbrk calls.
222 This malloc is NOT designed to work in multiprocessing applications.
223 No semaphores or other concurrency control are provided to ensure
224 that multiple malloc or free calls don't run at the same time,
225 which could be disasterous.
227 VERY heavy use of inlines is made, for clarity. If this malloc
228 is ported via a compiler without inlining capabilities, all
229 inlines should be transformed into macros -- making them non-inline
230 makes malloc at least twice as slow.
241 #include "//usr/include/stdio.h" /* needed for error reporting */
249 extern void* memset(void*, int, int);
250 extern void* memcpy(void*, const void*, int);
251 /*inline void bzero(void* s, int l) { memset(s, 0, l); }*/
253 /*extern void bzero(void*, unsigned int);*/
256 /*extern void bcopy(void*, void*, unsigned int);*/
258 extern void* sbrk(unsigned int);
260 /* Put this in instead of commmented out stuff above. */
261 #define bcopy(s,d,n) memcpy((d),(s),(n))
262 #define bcmp(s1,s2,n) memcmp((s1),(s2),(n))
263 #define bzero(s,n) memset((s),0,(n))
267 extern volatile void abort();
273 }; /* end of extern "C" */
277 /* A good multiple to call sbrk with */
279 #define SBRK_UNIT 4096
283 /* how to die on detected error */
286 static volatile void malloc_user_error()
288 static void malloc_user_error()
291 fputs("malloc/free/realloc: clobbered space detected\n", stderr); abort();
296 /* Basic overhead for each malloc'ed chunk */
301 unsigned int size; /* Size in bytes, including overhead. */
302 /* Or'ed with INUSE if in use. */
304 struct malloc_chunk* fd; /* double links -- used only if free. */
305 struct malloc_chunk* bk;
309 typedef struct malloc_chunk* mchunkptr;
313 struct malloc_chunk hd; /* dummy list header */
314 unsigned int dirty; /* True if maybe consolidatable */
315 /* Wasting a word here makes */
316 /* sizeof(bin) a power of 2, */
317 /* which makes size2bin() faster */
320 typedef struct malloc_bin* mbinptr;
323 /* sizes, alignments */
326 #define SIZE_SZ (sizeof(unsigned int))
327 #define MALLOC_MIN_OVERHEAD (SIZE_SZ + SIZE_SZ)
328 #define MALLOC_ALIGN_MASK (MALLOC_MIN_OVERHEAD - 1)
330 #define MINSIZE (sizeof(struct malloc_chunk) + SIZE_SZ) /* MUST == 16! */
333 /* pad request bytes into a usable size */
335 static inline unsigned int request2size(unsigned int request)
337 return (request == 0) ? MINSIZE :
338 ((request + MALLOC_MIN_OVERHEAD + MALLOC_ALIGN_MASK)
339 & ~(MALLOC_ALIGN_MASK));
343 static inline int aligned_OK(void* m)
345 return ((unsigned int)(m) & (MALLOC_ALIGN_MASK)) == 0;
349 /* size field or'd with INUSE when in use */
354 /* the bins, initialized to have null double linked lists */
356 #define MAXBIN 120 /* 1 more than needed for 32 bit addresses */
358 #define FIRSTBIN (&(av[0]))
360 static struct malloc_bin av[MAXBIN] =
362 { { 0, &(av[0].hd), &(av[0].hd) }, 0 },
363 { { 0, &(av[1].hd), &(av[1].hd) }, 0 },
364 { { 0, &(av[2].hd), &(av[2].hd) }, 0 },
365 { { 0, &(av[3].hd), &(av[3].hd) }, 0 },
366 { { 0, &(av[4].hd), &(av[4].hd) }, 0 },
367 { { 0, &(av[5].hd), &(av[5].hd) }, 0 },
368 { { 0, &(av[6].hd), &(av[6].hd) }, 0 },
369 { { 0, &(av[7].hd), &(av[7].hd) }, 0 },
370 { { 0, &(av[8].hd), &(av[8].hd) }, 0 },
371 { { 0, &(av[9].hd), &(av[9].hd) }, 0 },
373 { { 0, &(av[10].hd), &(av[10].hd) }, 0 },
374 { { 0, &(av[11].hd), &(av[11].hd) }, 0 },
375 { { 0, &(av[12].hd), &(av[12].hd) }, 0 },
376 { { 0, &(av[13].hd), &(av[13].hd) }, 0 },
377 { { 0, &(av[14].hd), &(av[14].hd) }, 0 },
378 { { 0, &(av[15].hd), &(av[15].hd) }, 0 },
379 { { 0, &(av[16].hd), &(av[16].hd) }, 0 },
380 { { 0, &(av[17].hd), &(av[17].hd) }, 0 },
381 { { 0, &(av[18].hd), &(av[18].hd) }, 0 },
382 { { 0, &(av[19].hd), &(av[19].hd) }, 0 },
384 { { 0, &(av[20].hd), &(av[20].hd) }, 0 },
385 { { 0, &(av[21].hd), &(av[21].hd) }, 0 },
386 { { 0, &(av[22].hd), &(av[22].hd) }, 0 },
387 { { 0, &(av[23].hd), &(av[23].hd) }, 0 },
388 { { 0, &(av[24].hd), &(av[24].hd) }, 0 },
389 { { 0, &(av[25].hd), &(av[25].hd) }, 0 },
390 { { 0, &(av[26].hd), &(av[26].hd) }, 0 },
391 { { 0, &(av[27].hd), &(av[27].hd) }, 0 },
392 { { 0, &(av[28].hd), &(av[28].hd) }, 0 },
393 { { 0, &(av[29].hd), &(av[29].hd) }, 0 },
395 { { 0, &(av[30].hd), &(av[30].hd) }, 0 },
396 { { 0, &(av[31].hd), &(av[31].hd) }, 0 },
397 { { 0, &(av[32].hd), &(av[32].hd) }, 0 },
398 { { 0, &(av[33].hd), &(av[33].hd) }, 0 },
399 { { 0, &(av[34].hd), &(av[34].hd) }, 0 },
400 { { 0, &(av[35].hd), &(av[35].hd) }, 0 },
401 { { 0, &(av[36].hd), &(av[36].hd) }, 0 },
402 { { 0, &(av[37].hd), &(av[37].hd) }, 0 },
403 { { 0, &(av[38].hd), &(av[38].hd) }, 0 },
404 { { 0, &(av[39].hd), &(av[39].hd) }, 0 },
406 { { 0, &(av[40].hd), &(av[40].hd) }, 0 },
407 { { 0, &(av[41].hd), &(av[41].hd) }, 0 },
408 { { 0, &(av[42].hd), &(av[42].hd) }, 0 },
409 { { 0, &(av[43].hd), &(av[43].hd) }, 0 },
410 { { 0, &(av[44].hd), &(av[44].hd) }, 0 },
411 { { 0, &(av[45].hd), &(av[45].hd) }, 0 },
412 { { 0, &(av[46].hd), &(av[46].hd) }, 0 },
413 { { 0, &(av[47].hd), &(av[47].hd) }, 0 },
414 { { 0, &(av[48].hd), &(av[48].hd) }, 0 },
415 { { 0, &(av[49].hd), &(av[49].hd) }, 0 },
417 { { 0, &(av[50].hd), &(av[50].hd) }, 0 },
418 { { 0, &(av[51].hd), &(av[51].hd) }, 0 },
419 { { 0, &(av[52].hd), &(av[52].hd) }, 0 },
420 { { 0, &(av[53].hd), &(av[53].hd) }, 0 },
421 { { 0, &(av[54].hd), &(av[54].hd) }, 0 },
422 { { 0, &(av[55].hd), &(av[55].hd) }, 0 },
423 { { 0, &(av[56].hd), &(av[56].hd) }, 0 },
424 { { 0, &(av[57].hd), &(av[57].hd) }, 0 },
425 { { 0, &(av[58].hd), &(av[58].hd) }, 0 },
426 { { 0, &(av[59].hd), &(av[59].hd) }, 0 },
428 { { 0, &(av[60].hd), &(av[60].hd) }, 0 },
429 { { 0, &(av[61].hd), &(av[61].hd) }, 0 },
430 { { 0, &(av[62].hd), &(av[62].hd) }, 0 },
431 { { 0, &(av[63].hd), &(av[63].hd) }, 0 },
432 { { 0, &(av[64].hd), &(av[64].hd) }, 0 },
433 { { 0, &(av[65].hd), &(av[65].hd) }, 0 },
434 { { 0, &(av[66].hd), &(av[66].hd) }, 0 },
435 { { 0, &(av[67].hd), &(av[67].hd) }, 0 },
436 { { 0, &(av[68].hd), &(av[68].hd) }, 0 },
437 { { 0, &(av[69].hd), &(av[69].hd) }, 0 },
439 { { 0, &(av[70].hd), &(av[70].hd) }, 0 },
440 { { 0, &(av[71].hd), &(av[71].hd) }, 0 },
441 { { 0, &(av[72].hd), &(av[72].hd) }, 0 },
442 { { 0, &(av[73].hd), &(av[73].hd) }, 0 },
443 { { 0, &(av[74].hd), &(av[74].hd) }, 0 },
444 { { 0, &(av[75].hd), &(av[75].hd) }, 0 },
445 { { 0, &(av[76].hd), &(av[76].hd) }, 0 },
446 { { 0, &(av[77].hd), &(av[77].hd) }, 0 },
447 { { 0, &(av[78].hd), &(av[78].hd) }, 0 },
448 { { 0, &(av[79].hd), &(av[79].hd) }, 0 },
450 { { 0, &(av[80].hd), &(av[80].hd) }, 0 },
451 { { 0, &(av[81].hd), &(av[81].hd) }, 0 },
452 { { 0, &(av[82].hd), &(av[82].hd) }, 0 },
453 { { 0, &(av[83].hd), &(av[83].hd) }, 0 },
454 { { 0, &(av[84].hd), &(av[84].hd) }, 0 },
455 { { 0, &(av[85].hd), &(av[85].hd) }, 0 },
456 { { 0, &(av[86].hd), &(av[86].hd) }, 0 },
457 { { 0, &(av[87].hd), &(av[87].hd) }, 0 },
458 { { 0, &(av[88].hd), &(av[88].hd) }, 0 },
459 { { 0, &(av[89].hd), &(av[89].hd) }, 0 },
461 { { 0, &(av[90].hd), &(av[90].hd) }, 0 },
462 { { 0, &(av[91].hd), &(av[91].hd) }, 0 },
463 { { 0, &(av[92].hd), &(av[92].hd) }, 0 },
464 { { 0, &(av[93].hd), &(av[93].hd) }, 0 },
465 { { 0, &(av[94].hd), &(av[94].hd) }, 0 },
466 { { 0, &(av[95].hd), &(av[95].hd) }, 0 },
467 { { 0, &(av[96].hd), &(av[96].hd) }, 0 },
468 { { 0, &(av[97].hd), &(av[97].hd) }, 0 },
469 { { 0, &(av[98].hd), &(av[98].hd) }, 0 },
470 { { 0, &(av[99].hd), &(av[99].hd) }, 0 },
472 { { 0, &(av[100].hd), &(av[100].hd) }, 0 },
473 { { 0, &(av[101].hd), &(av[101].hd) }, 0 },
474 { { 0, &(av[102].hd), &(av[102].hd) }, 0 },
475 { { 0, &(av[103].hd), &(av[103].hd) }, 0 },
476 { { 0, &(av[104].hd), &(av[104].hd) }, 0 },
477 { { 0, &(av[105].hd), &(av[105].hd) }, 0 },
478 { { 0, &(av[106].hd), &(av[106].hd) }, 0 },
479 { { 0, &(av[107].hd), &(av[107].hd) }, 0 },
480 { { 0, &(av[108].hd), &(av[108].hd) }, 0 },
481 { { 0, &(av[109].hd), &(av[109].hd) }, 0 },
483 { { 0, &(av[110].hd), &(av[110].hd) }, 0 },
484 { { 0, &(av[111].hd), &(av[111].hd) }, 0 },
485 { { 0, &(av[112].hd), &(av[112].hd) }, 0 },
486 { { 0, &(av[113].hd), &(av[113].hd) }, 0 },
487 { { 0, &(av[114].hd), &(av[114].hd) }, 0 },
488 { { 0, &(av[115].hd), &(av[115].hd) }, 0 },
489 { { 0, &(av[116].hd), &(av[116].hd) }, 0 },
490 { { 0, &(av[117].hd), &(av[117].hd) }, 0 },
491 { { 0, &(av[118].hd), &(av[118].hd) }, 0 },
492 { { 0, &(av[119].hd), &(av[119].hd) }, 0 }
499 static inline mbinptr size2bin(unsigned int sz)
502 while (sz >= (MINSIZE * 2)) { b += 4; sz >>= 1; } /* find power of 2 */
503 b += (sz - MINSIZE) >> 2; /* find quadrant */
509 /* counts maintained if MALLOC_STATS defined */
513 static unsigned int sbrked_mem;
514 static unsigned int requested_mem;
515 static unsigned int malloced_mem;
516 static unsigned int freed_mem;
517 static unsigned int max_used_mem;
519 static unsigned int n_sbrks;
520 static unsigned int n_mallocs;
521 static unsigned int n_frees;
522 static unsigned int n_reallocs;
523 static unsigned int n_reallocs_with_copy;
524 static unsigned int n_avail;
525 static unsigned int max_inuse;
527 static unsigned int n_malloc_chunks;
528 static unsigned int n_malloc_bins;
530 static unsigned int n_split;
531 static unsigned int n_consol;
534 static void do_malloc_stats(const mchunkptr p)
537 if ((n_mallocs-n_frees) > max_inuse)
538 max_inuse = n_mallocs - n_frees;
539 malloced_mem += (p->size & ~(INUSE));
540 if (malloced_mem - freed_mem > max_used_mem)
541 max_used_mem = malloced_mem - freed_mem;
544 static void do_free_stats(const mchunkptr p)
547 freed_mem += (p->size & ~(INUSE));
554 /* Utilities needed below for memalign */
555 /* This is redundant with libg++ support, but not if used stand-alone */
557 static unsigned int gcd(unsigned int a, unsigned int b)
563 tmp = a; a = b; b = tmp;
580 static inline unsigned int lcm(unsigned int x, unsigned int y)
582 return x / gcd(x, y) * y;
587 /* maintaining INUSE via size field */
590 #define inuse(p) ((p)->size & INUSE)
591 #define set_inuse(p) ((p)->size |= INUSE)
592 #define clear_inuse(b) ((p)->size &= ~INUSE)
595 /* operations on malloc_chunk addresses */
598 /* return ptr to next physical malloc_chunk */
600 #define next_chunk(p) ((mchunkptr)((char*)(p) + (p)->size))
602 /* return ptr to previous physical malloc_chunk */
604 #define prev_chunk(p) ((mchunkptr)((char*)(p)-((((int*)(p))[-1]) & ~(INUSE))))
606 /* place size at front and back of chunk */
609 static inline void set_size(mchunkptr p, unsigned int sz)
611 p->size = *((int*)((char*)(p) + sz - SIZE_SZ)) = sz;
617 /* conversion from malloc headers to user pointers, and back */
619 static inline void* chunk2mem(mchunkptr p)
623 mem = (void*)((char*)(p) + SIZE_SZ);
628 mchunkptr sanity_check(void* mem)
630 mchunkptr p = (mchunkptr)((char*)(mem) - SIZE_SZ);
632 /* a quick sanity check */
633 unsigned int sz = p->size & ~(INUSE);
634 if (p->size == sz || sz != *((int*)((char*)(p) + sz - SIZE_SZ)))
643 static inline mchunkptr mem2chunk(void* mem)
645 mchunkptr p = (mchunkptr)((char*)(mem) - SIZE_SZ);
647 /* a quick sanity check */
648 unsigned int sz = p->size & ~(INUSE);
649 if (p->size == sz || sz != *((int*)((char*)(p) + sz - SIZE_SZ)))
652 p->size = sz; /* clears INUSE */
658 /* maintaining bins & pointers */
661 /* maximum bin actually used */
663 static mbinptr malloc_maxbin = FIRSTBIN;
666 /* operations on lists inside bins */
669 /* take a chunk off a list */
671 static inline void unlink(mchunkptr p)
676 f->bk = b; b->fd = f;
678 UPDATE_STATS (--n_avail);
683 /* split a chunk and place on the back of a list */
685 static inline void split(mchunkptr p, unsigned int offset)
687 unsigned int room = p->size - offset;
690 mbinptr bn = size2bin(room); /* new bin */
691 mchunkptr h = &(bn->hd); /* its head */
692 mchunkptr b = h->bk; /* old back element */
693 mchunkptr t = (mchunkptr)((char*)(p) + offset); /* remaindered chunk */
696 t->size = *((int*)((char*)(t) + room - SIZE_SZ)) = room;
699 t->bk = b; t->fd = h; h->bk = b->fd = t;
701 /* adjust maxbin (h == b means was empty) */
702 if (h == b && bn > malloc_maxbin) malloc_maxbin = bn;
704 /* adjust size of chunk to be returned */
705 p->size = *((int*)((char*)(p) + offset - SIZE_SZ)) = offset;
707 UPDATE_STATS ((++n_split, ++n_avail));
713 /* place a consolidated chunk on the back of a list */
714 /* like above, except no split */
716 static inline void consollink(mchunkptr p)
718 mbinptr bn = size2bin(p->size);
719 mchunkptr h = &(bn->hd);
722 p->bk = b; p->fd = h; h->bk = b->fd = p;
724 if (h == b && bn > malloc_maxbin) malloc_maxbin = bn;
726 UPDATE_STATS(++n_avail);
730 /* place a freed chunk on the front of a list */
732 static inline void frontlink(mchunkptr p)
734 mbinptr bn = size2bin(p->size);
735 mchunkptr h = &(bn->hd);
738 p->bk = h; p->fd = f; f->bk = h->fd = p;
740 if (h == f && bn > malloc_maxbin) malloc_maxbin = bn;
744 UPDATE_STATS(++n_avail);
749 /* Dealing with sbrk */
752 /* To link consecutive sbrk regions when possible */
754 static int* last_sbrk_end;
757 /* who to call when sbrk returns failure */
759 #ifndef NO_NEW_HANDLER
760 typedef volatile void (*vfp)();
762 extern "C" vfp __new_handler;
764 extern vfp __new_handler;
768 static mchunkptr malloc_from_sys(unsigned nb)
771 unsigned int sbrk_size;
774 /* Minimally, we need to pad with enough space */
775 /* to place dummy size/use fields to ends if needed */
777 sbrk_size = ((nb + SBRK_UNIT - 1 + SIZE_SZ + SIZE_SZ)
778 / SBRK_UNIT) * SBRK_UNIT;
780 ip = (int*)(sbrk(sbrk_size));
781 if ((char*)ip == (char*)(-1)) /* sbrk returns -1 on failure */
783 #ifndef NO_NEW_HANDLER
789 UPDATE_STATS ((++n_sbrks, sbrked_mem += sbrk_size));
792 if (last_sbrk_end != &ip[-1])
794 /* It's either first time through or someone else called sbrk. */
795 /* Arrange end-markers at front & back */
797 /* Shouldn't be necessary, but better to be safe */
798 while (!aligned_OK(ip)) { ++ip; sbrk_size -= SIZE_SZ; }
801 /* Mark the front as in use to prevent merging. */
802 /* Note we can get away with only 1 word, not MINSIZE overhead here */
804 *ip++ = SIZE_SZ | INUSE;
807 set_size(p,sbrk_size - (SIZE_SZ + SIZE_SZ));
814 /* We can safely make the header start at end of prev sbrked chunk. */
815 /* We will still have space left at the end from a previous call */
816 /* to place the end marker, below */
818 p = (mchunkptr)(last_sbrk_end);
819 set_size(p, sbrk_size);
822 /* Even better, maybe we can merge with last fragment: */
828 set_size(l, p->size + l->size);
834 /* mark the end of sbrked space as in use to prevent merging */
836 last_sbrk_end = (int*)((char*)p + p->size);
837 *last_sbrk_end = SIZE_SZ | INUSE;
839 UPDATE_STATS((++n_avail, ++n_malloc_chunks));
841 /* make it safe to unlink in malloc */
842 UPDATE_STATS(++n_avail);
850 /* Consolidate dirty bins. */
851 /* Stop if found a chunk big enough to satisfy current malloc request */
853 /* (It requires much less bookkeeping to consolidate entire bins */
854 /* at once than to keep records of which chunks might be */
855 /* consolidatable. So long as the lists are short, which we */
856 /* try to ensure via small bin ranges, there is little wasted effort.) */
858 static mchunkptr malloc_find_space(unsigned int nb)
862 /* first, re-adjust max used bin */
864 while (malloc_maxbin >= FIRSTBIN &&
865 malloc_maxbin->hd.bk == &(malloc_maxbin->hd))
867 malloc_maxbin->dirty = 0;
871 for (b = malloc_maxbin; b >= FIRSTBIN; --b)
873 UPDATE_STATS(++n_malloc_bins);
877 mchunkptr h = &(b->hd); /* head of list */
878 mchunkptr p = h->fd; /* chunk traverser */
882 mchunkptr nextp = p->fd; /* save, in case of relinks */
883 int consolidated = 0; /* only unlink/relink if consolidated */
887 UPDATE_STATS(++n_malloc_chunks);
889 while (!inuse(t = prev_chunk(p))) /* consolidate backward */
891 if (!consolidated) { consolidated = 1; unlink(p); }
892 if (t == nextp) nextp = t->fd;
894 set_size(t, t->size + p->size);
896 UPDATE_STATS (++n_consol);
899 while (!inuse(t = next_chunk(p))) /* consolidate forward */
901 if (!consolidated) { consolidated = 1; unlink(p); }
902 if (t == nextp) nextp = t->fd;
904 set_size(p, p->size + t->size);
905 UPDATE_STATS (++n_consol);
912 /* make it safe to unlink in malloc */
913 UPDATE_STATS(++n_avail);
930 /* nothing available - sbrk some more */
932 return malloc_from_sys(nb);
937 /* Finally, the user-level functions */
939 void* malloc(unsigned int bytes)
941 unsigned int nb = request2size(bytes); /* padded request size */
942 mbinptr b = size2bin(nb); /* corresponding bin */
943 mchunkptr hd = &(b->hd); /* head of its list */
944 mchunkptr p = hd->fd; /* chunk traverser */
946 UPDATE_STATS((requested_mem+=bytes, ++n_malloc_bins));
948 /* Try a (near) exact match in own bin */
949 /* clean out unusable but consolidatable chunks in bin while traversing */
953 UPDATE_STATS(++n_malloc_chunks);
956 else /* try to consolidate; same code as malloc_find_space */
958 mchunkptr nextp = p->fd; /* save, in case of relinks */
959 int consolidated = 0; /* only unlink/relink if consolidated */
963 while (!inuse(t = prev_chunk(p))) /* consolidate backward */
965 if (!consolidated) { consolidated = 1; unlink(p); }
966 if (t == nextp) nextp = t->fd;
968 set_size(t, t->size + p->size);
970 UPDATE_STATS (++n_consol);
973 while (!inuse(t = next_chunk(p))) /* consolidate forward */
975 if (!consolidated) { consolidated = 1; unlink(p); }
976 if (t == nextp) nextp = t->fd;
978 set_size(p, p->size + t->size);
979 UPDATE_STATS (++n_consol);
986 /* make it safe to unlink again below */
987 UPDATE_STATS(++n_avail);
1000 b->dirty = 0; /* true if got here */
1002 /* Scan bigger bins for a victim */
1004 while (++b <= malloc_maxbin)
1006 UPDATE_STATS(++n_malloc_bins);
1007 if ((p = b->hd.bk) != &(b->hd)) /* no need to check size */
1011 /* Consolidate or sbrk */
1013 p = malloc_find_space(nb);
1015 if (p == 0) return 0; /* allocation failure */
1017 found: /* Use what we found */
1021 UPDATE_STATS(do_malloc_stats(p));
1022 return chunk2mem(p);
1028 void free(void* mem)
1032 mchunkptr p = mem2chunk(mem);
1033 UPDATE_STATS(do_free_stats(p));
1039 void* calloc(unsigned int n, unsigned int elem_size)
1041 unsigned int sz = n * elem_size;
1042 void* p = malloc(sz);
1047 /* This is here for compatibility with older systems */
1048 void cfree(void *mem)
1054 unsigned int malloc_usable_size(void* mem)
1060 mchunkptr p = (mchunkptr)((char*)(mem) - SIZE_SZ);
1061 unsigned int sz = p->size & ~(INUSE);
1062 if (p->size == sz || sz != *((int*)((char*)(p) + sz - SIZE_SZ)))
1065 return sz - MALLOC_MIN_OVERHEAD;
1071 void* realloc(void* mem, unsigned int bytes)
1074 return malloc(bytes);
1077 unsigned int nb = request2size(bytes);
1078 mchunkptr p = mem2chunk(mem);
1079 unsigned int oldsize = p->size;
1083 UPDATE_STATS((++n_reallocs, requested_mem += bytes-oldsize));
1085 /* try to expand (even if already big enough), to clean up chunk */
1087 while (!inuse(nxt = next_chunk(p)))
1089 UPDATE_STATS ((malloced_mem += nxt->size, ++n_consol));
1091 set_size(p, p->size + nxt->size);
1094 room = p->size - nb;
1098 UPDATE_STATS(malloced_mem -= room);
1099 return chunk2mem(p);
1101 else /* do the obvious */
1104 set_inuse(p); /* don't let malloc consolidate us yet! */
1105 newmem = malloc(nb);
1106 bcopy(mem, newmem, oldsize - SIZE_SZ);
1108 UPDATE_STATS(++n_reallocs_with_copy);
1116 /* return a pointer to space with at least the alignment requested */
1118 void* memalign(unsigned int alignment, unsigned int bytes)
1121 unsigned int nb = request2size(bytes);
1123 /* find an alignment that both we and the user can live with: */
1124 /* least common multiple guarantees mutual happiness */
1125 unsigned int align = lcm(alignment, MALLOC_MIN_OVERHEAD);
1126 unsigned int mask = align - 1;
1128 /* call malloc with worst case padding to hit alignment; */
1129 /* we will give back extra */
1131 unsigned int req = nb + align + MINSIZE;
1132 void* m = malloc(req);
1134 if (m == 0) return m;
1138 /* keep statistics on track */
1140 UPDATE_STATS(--n_mallocs);
1141 UPDATE_STATS(malloced_mem -= p->size);
1142 UPDATE_STATS(requested_mem -= req);
1143 UPDATE_STATS(requested_mem += bytes);
1145 if (((int)(m) & (mask)) != 0) /* misaligned */
1148 /* find an aligned spot inside chunk */
1150 mchunkptr ap = (mchunkptr)(( ((int)(m) + mask) & -align) - SIZE_SZ);
1152 unsigned int gap = (unsigned int)(ap) - (unsigned int)(p);
1155 /* we need to give back leading space in a chunk of at least MINSIZE */
1159 /* This works since align >= MINSIZE */
1160 /* and we've malloc'd enough total room */
1162 ap = (mchunkptr)( (int)(ap) + align );
1166 if (gap + nb > p->size) /* can't happen unless chunk sizes corrupted */
1167 malloc_user_error();
1169 room = p->size - gap;
1171 /* give back leader */
1180 /* also give back spare room at the end */
1183 UPDATE_STATS(do_malloc_stats(p));
1184 return chunk2mem(p);
1189 #include "getpagesize.h"
1192 static unsigned int malloc_pagesize = 0;
1194 void* valloc(unsigned int bytes)
1196 if (malloc_pagesize == 0) malloc_pagesize = getpagesize();
1197 return memalign (malloc_pagesize, bytes);
1203 #ifndef MALLOC_STATS
1208 double nm = (double)(n_mallocs + n_reallocs);
1210 fprintf(stderr, "\nmalloc statistics\n\n");
1213 fprintf(stderr, "requests = %10u total size = %10u\tave = %10u\n",
1214 n_mallocs, requested_mem, requested_mem/n_mallocs);
1217 fprintf(stderr, "mallocs = %10u total size = %10u\tave = %10u\n",
1218 n_mallocs, malloced_mem, malloced_mem/n_mallocs);
1221 fprintf(stderr, "frees = %10u total size = %10u\tave = %10u\n",
1222 n_frees, freed_mem, freed_mem/n_frees);
1224 if (n_mallocs-n_frees != 0)
1225 fprintf(stderr, "in use = %10u total size = %10u\tave = %10u\n",
1226 n_mallocs-n_frees, malloced_mem-freed_mem,
1227 (malloced_mem-freed_mem) / (n_mallocs-n_frees));
1230 fprintf(stderr, "max in use= %10u total size = %10u\tave = %10u\n",
1231 max_inuse, max_used_mem, max_used_mem / max_inuse);
1234 fprintf(stderr, "available = %10u total size = %10u\tave = %10u\n",
1235 n_avail, sbrked_mem - (malloced_mem-freed_mem),
1236 (sbrked_mem - (malloced_mem-freed_mem)) / n_avail);
1239 fprintf(stderr, "sbrks = %10u total size = %10u\tave = %10u\n\n",
1240 n_sbrks, sbrked_mem, sbrked_mem/ n_sbrks);
1242 if (n_reallocs != 0)
1243 fprintf(stderr, "reallocs = %10u with copy = %10u\n\n",
1244 n_reallocs, n_reallocs_with_copy);
1249 fprintf(stderr, "chunks scanned per malloc = %6.3f\n",
1250 n_malloc_chunks / nm);
1251 fprintf(stderr, "bins scanned per malloc = %6.3f\n",
1252 n_malloc_bins / nm);
1253 fprintf(stderr, "splits per malloc = %6.3f\n",
1255 fprintf(stderr, "consolidations per malloc = %6.3f\n",
1259 fprintf(stderr, "\nfree chunks:\n");
1260 for (i = 0; i < MAXBIN; ++i)
1263 if (p != &(av[i].hd))
1265 unsigned int count = 1;
1266 unsigned int sz = p->size;
1267 for (p = p->fd; p != &(av[i].hd); p = p->fd)
1273 fprintf(stderr, "\tsize = %10u count = %5u\n", sz, count);
1279 fprintf(stderr, "\tsize = %10u count = %5u\n", sz, count);
1284 #endif /* MALLOC_STATS */
1286 #endif /* NO_LIBGXX_MALLOC */