?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
bugfix for fortran compiler detection and setup
[charm.git] / src / conv-core / memory-gnuold.c
blob3f334ec927545a06d776fb86f40f5d6818f3f077
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
Charm++ is a parallel object-oriented programming language based on C++