malloc: dlmalloc: add an ability for the malloc to be re-init/init multiple times
[platform/kernel/u-boot.git] / common / dlmalloc.c
1 #include <common.h>
2
3 #if CONFIG_IS_ENABLED(UNIT_TEST)
4 #define DEBUG
5 #endif
6
7 #include <malloc.h>
8 #include <asm/io.h>
9
10 #ifdef DEBUG
11 #if __STD_C
12 static void malloc_update_mallinfo (void);
13 void malloc_stats (void);
14 #else
15 static void malloc_update_mallinfo ();
16 void malloc_stats();
17 #endif
18 #endif  /* DEBUG */
19
20 DECLARE_GLOBAL_DATA_PTR;
21
22 /*
23   Emulation of sbrk for WIN32
24   All code within the ifdef WIN32 is untested by me.
25
26   Thanks to Martin Fong and others for supplying this.
27 */
28
29
30 #ifdef WIN32
31
32 #define AlignPage(add) (((add) + (malloc_getpagesize-1)) & \
33 ~(malloc_getpagesize-1))
34 #define AlignPage64K(add) (((add) + (0x10000 - 1)) & ~(0x10000 - 1))
35
36 /* resrve 64MB to insure large contiguous space */
37 #define RESERVED_SIZE (1024*1024*64)
38 #define NEXT_SIZE (2048*1024)
39 #define TOP_MEMORY ((unsigned long)2*1024*1024*1024)
40
41 struct GmListElement;
42 typedef struct GmListElement GmListElement;
43
44 struct GmListElement
45 {
46         GmListElement* next;
47         void* base;
48 };
49
50 static GmListElement* head = 0;
51 static unsigned int gNextAddress = 0;
52 static unsigned int gAddressBase = 0;
53 static unsigned int gAllocatedSize = 0;
54
55 static
56 GmListElement* makeGmListElement (void* bas)
57 {
58         GmListElement* this;
59         this = (GmListElement*)(void*)LocalAlloc (0, sizeof (GmListElement));
60         assert (this);
61         if (this)
62         {
63                 this->base = bas;
64                 this->next = head;
65                 head = this;
66         }
67         return this;
68 }
69
70 void gcleanup ()
71 {
72         BOOL rval;
73         assert ( (head == NULL) || (head->base == (void*)gAddressBase));
74         if (gAddressBase && (gNextAddress - gAddressBase))
75         {
76                 rval = VirtualFree ((void*)gAddressBase,
77                                                         gNextAddress - gAddressBase,
78                                                         MEM_DECOMMIT);
79         assert (rval);
80         }
81         while (head)
82         {
83                 GmListElement* next = head->next;
84                 rval = VirtualFree (head->base, 0, MEM_RELEASE);
85                 assert (rval);
86                 LocalFree (head);
87                 head = next;
88         }
89 }
90
91 static
92 void* findRegion (void* start_address, unsigned long size)
93 {
94         MEMORY_BASIC_INFORMATION info;
95         if (size >= TOP_MEMORY) return NULL;
96
97         while ((unsigned long)start_address + size < TOP_MEMORY)
98         {
99                 VirtualQuery (start_address, &info, sizeof (info));
100                 if ((info.State == MEM_FREE) && (info.RegionSize >= size))
101                         return start_address;
102                 else
103                 {
104                         /* Requested region is not available so see if the */
105                         /* next region is available.  Set 'start_address' */
106                         /* to the next region and call 'VirtualQuery()' */
107                         /* again. */
108
109                         start_address = (char*)info.BaseAddress + info.RegionSize;
110
111                         /* Make sure we start looking for the next region */
112                         /* on the *next* 64K boundary.  Otherwise, even if */
113                         /* the new region is free according to */
114                         /* 'VirtualQuery()', the subsequent call to */
115                         /* 'VirtualAlloc()' (which follows the call to */
116                         /* this routine in 'wsbrk()') will round *down* */
117                         /* the requested address to a 64K boundary which */
118                         /* we already know is an address in the */
119                         /* unavailable region.  Thus, the subsequent call */
120                         /* to 'VirtualAlloc()' will fail and bring us back */
121                         /* here, causing us to go into an infinite loop. */
122
123                         start_address =
124                                 (void *) AlignPage64K((unsigned long) start_address);
125                 }
126         }
127         return NULL;
128
129 }
130
131
132 void* wsbrk (long size)
133 {
134         void* tmp;
135         if (size > 0)
136         {
137                 if (gAddressBase == 0)
138                 {
139                         gAllocatedSize = max (RESERVED_SIZE, AlignPage (size));
140                         gNextAddress = gAddressBase =
141                                 (unsigned int)VirtualAlloc (NULL, gAllocatedSize,
142                                                                                         MEM_RESERVE, PAGE_NOACCESS);
143                 } else if (AlignPage (gNextAddress + size) > (gAddressBase +
144 gAllocatedSize))
145                 {
146                         long new_size = max (NEXT_SIZE, AlignPage (size));
147                         void* new_address = (void*)(gAddressBase+gAllocatedSize);
148                         do
149                         {
150                                 new_address = findRegion (new_address, new_size);
151
152                                 if (!new_address)
153                                         return (void*)-1;
154
155                                 gAddressBase = gNextAddress =
156                                         (unsigned int)VirtualAlloc (new_address, new_size,
157                                                                                                 MEM_RESERVE, PAGE_NOACCESS);
158                                 /* repeat in case of race condition */
159                                 /* The region that we found has been snagged */
160                                 /* by another thread */
161                         }
162                         while (gAddressBase == 0);
163
164                         assert (new_address == (void*)gAddressBase);
165
166                         gAllocatedSize = new_size;
167
168                         if (!makeGmListElement ((void*)gAddressBase))
169                                 return (void*)-1;
170                 }
171                 if ((size + gNextAddress) > AlignPage (gNextAddress))
172                 {
173                         void* res;
174                         res = VirtualAlloc ((void*)AlignPage (gNextAddress),
175                                                                 (size + gNextAddress -
176                                                                  AlignPage (gNextAddress)),
177                                                                 MEM_COMMIT, PAGE_READWRITE);
178                         if (!res)
179                                 return (void*)-1;
180                 }
181                 tmp = (void*)gNextAddress;
182                 gNextAddress = (unsigned int)tmp + size;
183                 return tmp;
184         }
185         else if (size < 0)
186         {
187                 unsigned int alignedGoal = AlignPage (gNextAddress + size);
188                 /* Trim by releasing the virtual memory */
189                 if (alignedGoal >= gAddressBase)
190                 {
191                         VirtualFree ((void*)alignedGoal, gNextAddress - alignedGoal,
192                                                  MEM_DECOMMIT);
193                         gNextAddress = gNextAddress + size;
194                         return (void*)gNextAddress;
195                 }
196                 else
197                 {
198                         VirtualFree ((void*)gAddressBase, gNextAddress - gAddressBase,
199                                                  MEM_DECOMMIT);
200                         gNextAddress = gAddressBase;
201                         return (void*)-1;
202                 }
203         }
204         else
205         {
206                 return (void*)gNextAddress;
207         }
208 }
209
210 #endif
211
212
213
214 /*
215   Type declarations
216 */
217
218
219 struct malloc_chunk
220 {
221   INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */
222   INTERNAL_SIZE_T size;      /* Size in bytes, including overhead. */
223   struct malloc_chunk* fd;   /* double links -- used only if free. */
224   struct malloc_chunk* bk;
225 } __attribute__((__may_alias__)) ;
226
227 typedef struct malloc_chunk* mchunkptr;
228
229 /*
230
231    malloc_chunk details:
232
233     (The following includes lightly edited explanations by Colin Plumb.)
234
235     Chunks of memory are maintained using a `boundary tag' method as
236     described in e.g., Knuth or Standish.  (See the paper by Paul
237     Wilson ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a
238     survey of such techniques.)  Sizes of free chunks are stored both
239     in the front of each chunk and at the end.  This makes
240     consolidating fragmented chunks into bigger chunks very fast.  The
241     size fields also hold bits representing whether chunks are free or
242     in use.
243
244     An allocated chunk looks like this:
245
246
247     chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
248             |             Size of previous chunk, if allocated            | |
249             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
250             |             Size of chunk, in bytes                         |P|
251       mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
252             |             User data starts here...                          .
253             .                                                               .
254             .             (malloc_usable_space() bytes)                     .
255             .                                                               |
256 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
257             |             Size of chunk                                     |
258             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
259
260
261     Where "chunk" is the front of the chunk for the purpose of most of
262     the malloc code, but "mem" is the pointer that is returned to the
263     user.  "Nextchunk" is the beginning of the next contiguous chunk.
264
265     Chunks always begin on even word boundries, so the mem portion
266     (which is returned to the user) is also on an even word boundary, and
267     thus double-word aligned.
268
269     Free chunks are stored in circular doubly-linked lists, and look like this:
270
271     chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
272             |             Size of previous chunk                            |
273             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
274     `head:' |             Size of chunk, in bytes                         |P|
275       mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
276             |             Forward pointer to next chunk in list             |
277             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
278             |             Back pointer to previous chunk in list            |
279             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
280             |             Unused space (may be 0 bytes long)                .
281             .                                                               .
282             .                                                               |
283
284 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
285     `foot:' |             Size of chunk, in bytes                           |
286             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
287
288     The P (PREV_INUSE) bit, stored in the unused low-order bit of the
289     chunk size (which is always a multiple of two words), is an in-use
290     bit for the *previous* chunk.  If that bit is *clear*, then the
291     word before the current chunk size contains the previous chunk
292     size, and can be used to find the front of the previous chunk.
293     (The very first chunk allocated always has this bit set,
294     preventing access to non-existent (or non-owned) memory.)
295
296     Note that the `foot' of the current chunk is actually represented
297     as the prev_size of the NEXT chunk. (This makes it easier to
298     deal with alignments etc).
299
300     The two exceptions to all this are
301
302      1. The special chunk `top', which doesn't bother using the
303         trailing size field since there is no
304         next contiguous chunk that would have to index off it. (After
305         initialization, `top' is forced to always exist.  If it would
306         become less than MINSIZE bytes long, it is replenished via
307         malloc_extend_top.)
308
309      2. Chunks allocated via mmap, which have the second-lowest-order
310         bit (IS_MMAPPED) set in their size fields.  Because they are
311         never merged or traversed from any other chunk, they have no
312         foot size or inuse information.
313
314     Available chunks are kept in any of several places (all declared below):
315
316     * `av': An array of chunks serving as bin headers for consolidated
317        chunks. Each bin is doubly linked.  The bins are approximately
318        proportionally (log) spaced.  There are a lot of these bins
319        (128). This may look excessive, but works very well in
320        practice.  All procedures maintain the invariant that no
321        consolidated chunk physically borders another one. Chunks in
322        bins are kept in size order, with ties going to the
323        approximately least recently used chunk.
324
325        The chunks in each bin are maintained in decreasing sorted order by
326        size.  This is irrelevant for the small bins, which all contain
327        the same-sized chunks, but facilitates best-fit allocation for
328        larger chunks. (These lists are just sequential. Keeping them in
329        order almost never requires enough traversal to warrant using
330        fancier ordered data structures.)  Chunks of the same size are
331        linked with the most recently freed at the front, and allocations
332        are taken from the back.  This results in LRU or FIFO allocation
333        order, which tends to give each chunk an equal opportunity to be
334        consolidated with adjacent freed chunks, resulting in larger free
335        chunks and less fragmentation.
336
337     * `top': The top-most available chunk (i.e., the one bordering the
338        end of available memory) is treated specially. It is never
339        included in any bin, is used only if no other chunk is
340        available, and is released back to the system if it is very
341        large (see M_TRIM_THRESHOLD).
342
343     * `last_remainder': A bin holding only the remainder of the
344        most recently split (non-top) chunk. This bin is checked
345        before other non-fitting chunks, so as to provide better
346        locality for runs of sequentially allocated chunks.
347
348     *  Implicitly, through the host system's memory mapping tables.
349        If supported, requests greater than a threshold are usually
350        serviced via calls to mmap, and then later released via munmap.
351
352 */
353
354 /*  sizes, alignments */
355
356 #define SIZE_SZ                (sizeof(INTERNAL_SIZE_T))
357 #define MALLOC_ALIGNMENT       (SIZE_SZ + SIZE_SZ)
358 #define MALLOC_ALIGN_MASK      (MALLOC_ALIGNMENT - 1)
359 #define MINSIZE                (sizeof(struct malloc_chunk))
360
361 /* conversion from malloc headers to user pointers, and back */
362
363 #define chunk2mem(p)   ((Void_t*)((char*)(p) + 2*SIZE_SZ))
364 #define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2*SIZE_SZ))
365
366 /* pad request bytes into a usable size */
367
368 #define request2size(req) \
369  (((long)((req) + (SIZE_SZ + MALLOC_ALIGN_MASK)) < \
370   (long)(MINSIZE + MALLOC_ALIGN_MASK)) ? MINSIZE : \
371    (((req) + (SIZE_SZ + MALLOC_ALIGN_MASK)) & ~(MALLOC_ALIGN_MASK)))
372
373 /* Check if m has acceptable alignment */
374
375 #define aligned_OK(m)    (((unsigned long)((m)) & (MALLOC_ALIGN_MASK)) == 0)
376
377
378
379
380 /*
381   Physical chunk operations
382 */
383
384
385 /* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */
386
387 #define PREV_INUSE 0x1
388
389 /* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap() */
390
391 #define IS_MMAPPED 0x2
392
393 /* Bits to mask off when extracting size */
394
395 #define SIZE_BITS (PREV_INUSE|IS_MMAPPED)
396
397
398 /* Ptr to next physical malloc_chunk. */
399
400 #define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->size & ~PREV_INUSE) ))
401
402 /* Ptr to previous physical malloc_chunk */
403
404 #define prev_chunk(p)\
405    ((mchunkptr)( ((char*)(p)) - ((p)->prev_size) ))
406
407
408 /* Treat space at ptr + offset as a chunk */
409
410 #define chunk_at_offset(p, s)  ((mchunkptr)(((char*)(p)) + (s)))
411
412
413
414
415 /*
416   Dealing with use bits
417 */
418
419 /* extract p's inuse bit */
420
421 #define inuse(p)\
422 ((((mchunkptr)(((char*)(p))+((p)->size & ~PREV_INUSE)))->size) & PREV_INUSE)
423
424 /* extract inuse bit of previous chunk */
425
426 #define prev_inuse(p)  ((p)->size & PREV_INUSE)
427
428 /* check for mmap()'ed chunk */
429
430 #define chunk_is_mmapped(p) ((p)->size & IS_MMAPPED)
431
432 /* set/clear chunk as in use without otherwise disturbing */
433
434 #define set_inuse(p)\
435 ((mchunkptr)(((char*)(p)) + ((p)->size & ~PREV_INUSE)))->size |= PREV_INUSE
436
437 #define clear_inuse(p)\
438 ((mchunkptr)(((char*)(p)) + ((p)->size & ~PREV_INUSE)))->size &= ~(PREV_INUSE)
439
440 /* check/set/clear inuse bits in known places */
441
442 #define inuse_bit_at_offset(p, s)\
443  (((mchunkptr)(((char*)(p)) + (s)))->size & PREV_INUSE)
444
445 #define set_inuse_bit_at_offset(p, s)\
446  (((mchunkptr)(((char*)(p)) + (s)))->size |= PREV_INUSE)
447
448 #define clear_inuse_bit_at_offset(p, s)\
449  (((mchunkptr)(((char*)(p)) + (s)))->size &= ~(PREV_INUSE))
450
451
452
453
454 /*
455   Dealing with size fields
456 */
457
458 /* Get size, ignoring use bits */
459
460 #define chunksize(p)          ((p)->size & ~(SIZE_BITS))
461
462 /* Set size at head, without disturbing its use bit */
463
464 #define set_head_size(p, s)   ((p)->size = (((p)->size & PREV_INUSE) | (s)))
465
466 /* Set size/use ignoring previous bits in header */
467
468 #define set_head(p, s)        ((p)->size = (s))
469
470 /* Set size at footer (only when chunk is not in use) */
471
472 #define set_foot(p, s)   (((mchunkptr)((char*)(p) + (s)))->prev_size = (s))
473
474
475
476
477
478 /*
479    Bins
480
481     The bins, `av_' are an array of pairs of pointers serving as the
482     heads of (initially empty) doubly-linked lists of chunks, laid out
483     in a way so that each pair can be treated as if it were in a
484     malloc_chunk. (This way, the fd/bk offsets for linking bin heads
485     and chunks are the same).
486
487     Bins for sizes < 512 bytes contain chunks of all the same size, spaced
488     8 bytes apart. Larger bins are approximately logarithmically
489     spaced. (See the table below.) The `av_' array is never mentioned
490     directly in the code, but instead via bin access macros.
491
492     Bin layout:
493
494     64 bins of size       8
495     32 bins of size      64
496     16 bins of size     512
497      8 bins of size    4096
498      4 bins of size   32768
499      2 bins of size  262144
500      1 bin  of size what's left
501
502     There is actually a little bit of slop in the numbers in bin_index
503     for the sake of speed. This makes no difference elsewhere.
504
505     The special chunks `top' and `last_remainder' get their own bins,
506     (this is implemented via yet more trickery with the av_ array),
507     although `top' is never properly linked to its bin since it is
508     always handled specially.
509
510 */
511
512 #define NAV             128   /* number of bins */
513
514 typedef struct malloc_chunk* mbinptr;
515
516 /* access macros */
517
518 #define bin_at(i)      ((mbinptr)((char*)&(av_[2*(i) + 2]) - 2*SIZE_SZ))
519 #define next_bin(b)    ((mbinptr)((char*)(b) + 2 * sizeof(mbinptr)))
520 #define prev_bin(b)    ((mbinptr)((char*)(b) - 2 * sizeof(mbinptr)))
521
522 /*
523    The first 2 bins are never indexed. The corresponding av_ cells are instead
524    used for bookkeeping. This is not to save space, but to simplify
525    indexing, maintain locality, and avoid some initialization tests.
526 */
527
528 #define top            (av_[2])          /* The topmost chunk */
529 #define last_remainder (bin_at(1))       /* remainder from last split */
530
531
532 /*
533    Because top initially points to its own bin with initial
534    zero size, thus forcing extension on the first malloc request,
535    we avoid having any special code in malloc to check whether
536    it even exists yet. But we still need to in malloc_extend_top.
537 */
538
539 #define initial_top    ((mchunkptr)(bin_at(0)))
540
541 /* Helper macro to initialize bins */
542
543 #define IAV(i)  bin_at(i), bin_at(i)
544
545 static mbinptr av_[NAV * 2 + 2] = {
546  NULL, NULL,
547  IAV(0),   IAV(1),   IAV(2),   IAV(3),   IAV(4),   IAV(5),   IAV(6),   IAV(7),
548  IAV(8),   IAV(9),   IAV(10),  IAV(11),  IAV(12),  IAV(13),  IAV(14),  IAV(15),
549  IAV(16),  IAV(17),  IAV(18),  IAV(19),  IAV(20),  IAV(21),  IAV(22),  IAV(23),
550  IAV(24),  IAV(25),  IAV(26),  IAV(27),  IAV(28),  IAV(29),  IAV(30),  IAV(31),
551  IAV(32),  IAV(33),  IAV(34),  IAV(35),  IAV(36),  IAV(37),  IAV(38),  IAV(39),
552  IAV(40),  IAV(41),  IAV(42),  IAV(43),  IAV(44),  IAV(45),  IAV(46),  IAV(47),
553  IAV(48),  IAV(49),  IAV(50),  IAV(51),  IAV(52),  IAV(53),  IAV(54),  IAV(55),
554  IAV(56),  IAV(57),  IAV(58),  IAV(59),  IAV(60),  IAV(61),  IAV(62),  IAV(63),
555  IAV(64),  IAV(65),  IAV(66),  IAV(67),  IAV(68),  IAV(69),  IAV(70),  IAV(71),
556  IAV(72),  IAV(73),  IAV(74),  IAV(75),  IAV(76),  IAV(77),  IAV(78),  IAV(79),
557  IAV(80),  IAV(81),  IAV(82),  IAV(83),  IAV(84),  IAV(85),  IAV(86),  IAV(87),
558  IAV(88),  IAV(89),  IAV(90),  IAV(91),  IAV(92),  IAV(93),  IAV(94),  IAV(95),
559  IAV(96),  IAV(97),  IAV(98),  IAV(99),  IAV(100), IAV(101), IAV(102), IAV(103),
560  IAV(104), IAV(105), IAV(106), IAV(107), IAV(108), IAV(109), IAV(110), IAV(111),
561  IAV(112), IAV(113), IAV(114), IAV(115), IAV(116), IAV(117), IAV(118), IAV(119),
562  IAV(120), IAV(121), IAV(122), IAV(123), IAV(124), IAV(125), IAV(126), IAV(127)
563 };
564
565 #ifdef CONFIG_NEEDS_MANUAL_RELOC
566 static void malloc_bin_reloc(void)
567 {
568         mbinptr *p = &av_[2];
569         size_t i;
570
571         for (i = 2; i < ARRAY_SIZE(av_); ++i, ++p)
572                 *p = (mbinptr)((ulong)*p + gd->reloc_off);
573 }
574 #else
575 static inline void malloc_bin_reloc(void) {}
576 #endif
577
578 #ifdef CONFIG_SYS_MALLOC_DEFAULT_TO_INIT
579 static void malloc_init(void);
580 #endif
581
582 ulong mem_malloc_start = 0;
583 ulong mem_malloc_end = 0;
584 ulong mem_malloc_brk = 0;
585
586 void *sbrk(ptrdiff_t increment)
587 {
588         ulong old = mem_malloc_brk;
589         ulong new = old + increment;
590
591         /*
592          * if we are giving memory back make sure we clear it out since
593          * we set MORECORE_CLEARS to 1
594          */
595         if (increment < 0)
596                 memset((void *)new, 0, -increment);
597
598         if ((new < mem_malloc_start) || (new > mem_malloc_end))
599                 return (void *)MORECORE_FAILURE;
600
601         mem_malloc_brk = new;
602
603         return (void *)old;
604 }
605
606 void mem_malloc_init(ulong start, ulong size)
607 {
608         mem_malloc_start = start;
609         mem_malloc_end = start + size;
610         mem_malloc_brk = start;
611
612 #ifdef CONFIG_SYS_MALLOC_DEFAULT_TO_INIT
613         malloc_init();
614 #endif
615
616         debug("using memory %#lx-%#lx for malloc()\n", mem_malloc_start,
617               mem_malloc_end);
618 #ifdef CONFIG_SYS_MALLOC_CLEAR_ON_INIT
619         memset((void *)mem_malloc_start, 0x0, size);
620 #endif
621         malloc_bin_reloc();
622 }
623
624 /* field-extraction macros */
625
626 #define first(b) ((b)->fd)
627 #define last(b)  ((b)->bk)
628
629 /*
630   Indexing into bins
631 */
632
633 #define bin_index(sz)                                                          \
634 (((((unsigned long)(sz)) >> 9) ==    0) ?       (((unsigned long)(sz)) >>  3): \
635  ((((unsigned long)(sz)) >> 9) <=    4) ?  56 + (((unsigned long)(sz)) >>  6): \
636  ((((unsigned long)(sz)) >> 9) <=   20) ?  91 + (((unsigned long)(sz)) >>  9): \
637  ((((unsigned long)(sz)) >> 9) <=   84) ? 110 + (((unsigned long)(sz)) >> 12): \
638  ((((unsigned long)(sz)) >> 9) <=  340) ? 119 + (((unsigned long)(sz)) >> 15): \
639  ((((unsigned long)(sz)) >> 9) <= 1364) ? 124 + (((unsigned long)(sz)) >> 18): \
640                                           126)
641 /*
642   bins for chunks < 512 are all spaced 8 bytes apart, and hold
643   identically sized chunks. This is exploited in malloc.
644 */
645
646 #define MAX_SMALLBIN         63
647 #define MAX_SMALLBIN_SIZE   512
648 #define SMALLBIN_WIDTH        8
649
650 #define smallbin_index(sz)  (((unsigned long)(sz)) >> 3)
651
652 /*
653    Requests are `small' if both the corresponding and the next bin are small
654 */
655
656 #define is_small_request(nb) (nb < MAX_SMALLBIN_SIZE - SMALLBIN_WIDTH)
657
658
659
660 /*
661     To help compensate for the large number of bins, a one-level index
662     structure is used for bin-by-bin searching.  `binblocks' is a
663     one-word bitvector recording whether groups of BINBLOCKWIDTH bins
664     have any (possibly) non-empty bins, so they can be skipped over
665     all at once during during traversals. The bits are NOT always
666     cleared as soon as all bins in a block are empty, but instead only
667     when all are noticed to be empty during traversal in malloc.
668 */
669
670 #define BINBLOCKWIDTH     4   /* bins per block */
671
672 #define binblocks_r     ((INTERNAL_SIZE_T)av_[1]) /* bitvector of nonempty blocks */
673 #define binblocks_w     (av_[1])
674
675 /* bin<->block macros */
676
677 #define idx2binblock(ix)    ((unsigned)1 << (ix / BINBLOCKWIDTH))
678 #define mark_binblock(ii)   (binblocks_w = (mbinptr)(binblocks_r | idx2binblock(ii)))
679 #define clear_binblock(ii)  (binblocks_w = (mbinptr)(binblocks_r & ~(idx2binblock(ii))))
680
681
682
683
684
685 /*  Other static bookkeeping data */
686
687 /* variables holding tunable values */
688
689 static unsigned long trim_threshold   = DEFAULT_TRIM_THRESHOLD;
690 static unsigned long top_pad          = DEFAULT_TOP_PAD;
691 static unsigned int  n_mmaps_max      = DEFAULT_MMAP_MAX;
692 static unsigned long mmap_threshold   = DEFAULT_MMAP_THRESHOLD;
693
694 /* The first value returned from sbrk */
695 static char* sbrk_base = (char*)(-1);
696
697 /* The maximum memory obtained from system via sbrk */
698 static unsigned long max_sbrked_mem = 0;
699
700 /* The maximum via either sbrk or mmap */
701 static unsigned long max_total_mem = 0;
702
703 /* internal working copy of mallinfo */
704 static struct mallinfo current_mallinfo = {  0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
705
706 /* The total memory obtained from system via sbrk */
707 #define sbrked_mem  (current_mallinfo.arena)
708
709 /* Tracking mmaps */
710
711 #ifdef DEBUG
712 static unsigned int n_mmaps = 0;
713 #endif  /* DEBUG */
714 static unsigned long mmapped_mem = 0;
715 #if HAVE_MMAP
716 static unsigned int max_n_mmaps = 0;
717 static unsigned long max_mmapped_mem = 0;
718 #endif
719
720 #ifdef CONFIG_SYS_MALLOC_DEFAULT_TO_INIT
721 static void malloc_init(void)
722 {
723         int i, j;
724
725         debug("bins (av_ array) are at %p\n", (void *)av_);
726
727         av_[0] = NULL; av_[1] = NULL;
728         for (i = 2, j = 2; i < NAV * 2 + 2; i += 2, j++) {
729                 av_[i] = bin_at(j - 2);
730                 av_[i + 1] = bin_at(j - 2);
731
732                 /* Just print the first few bins so that
733                  * we can see there are alright.
734                  */
735                 if (i < 10)
736                         debug("av_[%d]=%lx av_[%d]=%lx\n",
737                               i, (ulong)av_[i],
738                               i + 1, (ulong)av_[i + 1]);
739         }
740
741         /* Init the static bookkeeping as well */
742         sbrk_base = (char *)(-1);
743         max_sbrked_mem = 0;
744         max_total_mem = 0;
745 #ifdef DEBUG
746         memset((void *)&current_mallinfo, 0, sizeof(struct mallinfo));
747 #endif
748 }
749 #endif
750
751 /*
752   Debugging support
753 */
754
755 #ifdef DEBUG
756
757
758 /*
759   These routines make a number of assertions about the states
760   of data structures that should be true at all times. If any
761   are not true, it's very likely that a user program has somehow
762   trashed memory. (It's also possible that there is a coding error
763   in malloc. In which case, please report it!)
764 */
765
766 #if __STD_C
767 static void do_check_chunk(mchunkptr p)
768 #else
769 static void do_check_chunk(p) mchunkptr p;
770 #endif
771 {
772   INTERNAL_SIZE_T sz = p->size & ~PREV_INUSE;
773
774   /* No checkable chunk is mmapped */
775   assert(!chunk_is_mmapped(p));
776
777   /* Check for legal address ... */
778   assert((char*)p >= sbrk_base);
779   if (p != top)
780     assert((char*)p + sz <= (char*)top);
781   else
782     assert((char*)p + sz <= sbrk_base + sbrked_mem);
783
784 }
785
786
787 #if __STD_C
788 static void do_check_free_chunk(mchunkptr p)
789 #else
790 static void do_check_free_chunk(p) mchunkptr p;
791 #endif
792 {
793   INTERNAL_SIZE_T sz = p->size & ~PREV_INUSE;
794   mchunkptr next = chunk_at_offset(p, sz);
795
796   do_check_chunk(p);
797
798   /* Check whether it claims to be free ... */
799   assert(!inuse(p));
800
801   /* Unless a special marker, must have OK fields */
802   if ((long)sz >= (long)MINSIZE)
803   {
804     assert((sz & MALLOC_ALIGN_MASK) == 0);
805     assert(aligned_OK(chunk2mem(p)));
806     /* ... matching footer field */
807     assert(next->prev_size == sz);
808     /* ... and is fully consolidated */
809     assert(prev_inuse(p));
810     assert (next == top || inuse(next));
811
812     /* ... and has minimally sane links */
813     assert(p->fd->bk == p);
814     assert(p->bk->fd == p);
815   }
816   else /* markers are always of size SIZE_SZ */
817     assert(sz == SIZE_SZ);
818 }
819
820 #if __STD_C
821 static void do_check_inuse_chunk(mchunkptr p)
822 #else
823 static void do_check_inuse_chunk(p) mchunkptr p;
824 #endif
825 {
826   mchunkptr next = next_chunk(p);
827   do_check_chunk(p);
828
829   /* Check whether it claims to be in use ... */
830   assert(inuse(p));
831
832   /* ... and is surrounded by OK chunks.
833     Since more things can be checked with free chunks than inuse ones,
834     if an inuse chunk borders them and debug is on, it's worth doing them.
835   */
836   if (!prev_inuse(p))
837   {
838     mchunkptr prv = prev_chunk(p);
839     assert(next_chunk(prv) == p);
840     do_check_free_chunk(prv);
841   }
842   if (next == top)
843   {
844     assert(prev_inuse(next));
845     assert(chunksize(next) >= MINSIZE);
846   }
847   else if (!inuse(next))
848     do_check_free_chunk(next);
849
850 }
851
852 #if __STD_C
853 static void do_check_malloced_chunk(mchunkptr p, INTERNAL_SIZE_T s)
854 #else
855 static void do_check_malloced_chunk(p, s) mchunkptr p; INTERNAL_SIZE_T s;
856 #endif
857 {
858   INTERNAL_SIZE_T sz = p->size & ~PREV_INUSE;
859   long room = sz - s;
860
861   do_check_inuse_chunk(p);
862
863   /* Legal size ... */
864   assert((long)sz >= (long)MINSIZE);
865   assert((sz & MALLOC_ALIGN_MASK) == 0);
866   assert(room >= 0);
867   assert(room < (long)MINSIZE);
868
869   /* ... and alignment */
870   assert(aligned_OK(chunk2mem(p)));
871
872
873   /* ... and was allocated at front of an available chunk */
874   assert(prev_inuse(p));
875
876 }
877
878
879 #define check_free_chunk(P)  do_check_free_chunk(P)
880 #define check_inuse_chunk(P) do_check_inuse_chunk(P)
881 #define check_chunk(P) do_check_chunk(P)
882 #define check_malloced_chunk(P,N) do_check_malloced_chunk(P,N)
883 #else
884 #define check_free_chunk(P)
885 #define check_inuse_chunk(P)
886 #define check_chunk(P)
887 #define check_malloced_chunk(P,N)
888 #endif
889
890
891
892 /*
893   Macro-based internal utilities
894 */
895
896
897 /*
898   Linking chunks in bin lists.
899   Call these only with variables, not arbitrary expressions, as arguments.
900 */
901
902 /*
903   Place chunk p of size s in its bin, in size order,
904   putting it ahead of others of same size.
905 */
906
907
908 #define frontlink(P, S, IDX, BK, FD)                                          \
909 {                                                                             \
910   if (S < MAX_SMALLBIN_SIZE)                                                  \
911   {                                                                           \
912     IDX = smallbin_index(S);                                                  \
913     mark_binblock(IDX);                                                       \
914     BK = bin_at(IDX);                                                         \
915     FD = BK->fd;                                                              \
916     P->bk = BK;                                                               \
917     P->fd = FD;                                                               \
918     FD->bk = BK->fd = P;                                                      \
919   }                                                                           \
920   else                                                                        \
921   {                                                                           \
922     IDX = bin_index(S);                                                       \
923     BK = bin_at(IDX);                                                         \
924     FD = BK->fd;                                                              \
925     if (FD == BK) mark_binblock(IDX);                                         \
926     else                                                                      \
927     {                                                                         \
928       while (FD != BK && S < chunksize(FD)) FD = FD->fd;                      \
929       BK = FD->bk;                                                            \
930     }                                                                         \
931     P->bk = BK;                                                               \
932     P->fd = FD;                                                               \
933     FD->bk = BK->fd = P;                                                      \
934   }                                                                           \
935 }
936
937
938 /* take a chunk off a list */
939
940 #define unlink(P, BK, FD)                                                     \
941 {                                                                             \
942   BK = P->bk;                                                                 \
943   FD = P->fd;                                                                 \
944   FD->bk = BK;                                                                \
945   BK->fd = FD;                                                                \
946 }                                                                             \
947
948 /* Place p as the last remainder */
949
950 #define link_last_remainder(P)                                                \
951 {                                                                             \
952   last_remainder->fd = last_remainder->bk =  P;                               \
953   P->fd = P->bk = last_remainder;                                             \
954 }
955
956 /* Clear the last_remainder bin */
957
958 #define clear_last_remainder \
959   (last_remainder->fd = last_remainder->bk = last_remainder)
960
961
962
963
964
965 /* Routines dealing with mmap(). */
966
967 #if HAVE_MMAP
968
969 #if __STD_C
970 static mchunkptr mmap_chunk(size_t size)
971 #else
972 static mchunkptr mmap_chunk(size) size_t size;
973 #endif
974 {
975   size_t page_mask = malloc_getpagesize - 1;
976   mchunkptr p;
977
978 #ifndef MAP_ANONYMOUS
979   static int fd = -1;
980 #endif
981
982   if(n_mmaps >= n_mmaps_max) return 0; /* too many regions */
983
984   /* For mmapped chunks, the overhead is one SIZE_SZ unit larger, because
985    * there is no following chunk whose prev_size field could be used.
986    */
987   size = (size + SIZE_SZ + page_mask) & ~page_mask;
988
989 #ifdef MAP_ANONYMOUS
990   p = (mchunkptr)mmap(0, size, PROT_READ|PROT_WRITE,
991                       MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
992 #else /* !MAP_ANONYMOUS */
993   if (fd < 0)
994   {
995     fd = open("/dev/zero", O_RDWR);
996     if(fd < 0) return 0;
997   }
998   p = (mchunkptr)mmap(0, size, PROT_READ|PROT_WRITE, MAP_PRIVATE, fd, 0);
999 #endif
1000
1001   if(p == (mchunkptr)-1) return 0;
1002
1003   n_mmaps++;
1004   if (n_mmaps > max_n_mmaps) max_n_mmaps = n_mmaps;
1005
1006   /* We demand that eight bytes into a page must be 8-byte aligned. */
1007   assert(aligned_OK(chunk2mem(p)));
1008
1009   /* The offset to the start of the mmapped region is stored
1010    * in the prev_size field of the chunk; normally it is zero,
1011    * but that can be changed in memalign().
1012    */
1013   p->prev_size = 0;
1014   set_head(p, size|IS_MMAPPED);
1015
1016   mmapped_mem += size;
1017   if ((unsigned long)mmapped_mem > (unsigned long)max_mmapped_mem)
1018     max_mmapped_mem = mmapped_mem;
1019   if ((unsigned long)(mmapped_mem + sbrked_mem) > (unsigned long)max_total_mem)
1020     max_total_mem = mmapped_mem + sbrked_mem;
1021   return p;
1022 }
1023
1024 #if __STD_C
1025 static void munmap_chunk(mchunkptr p)
1026 #else
1027 static void munmap_chunk(p) mchunkptr p;
1028 #endif
1029 {
1030   INTERNAL_SIZE_T size = chunksize(p);
1031   int ret;
1032
1033   assert (chunk_is_mmapped(p));
1034   assert(! ((char*)p >= sbrk_base && (char*)p < sbrk_base + sbrked_mem));
1035   assert((n_mmaps > 0));
1036   assert(((p->prev_size + size) & (malloc_getpagesize-1)) == 0);
1037
1038   n_mmaps--;
1039   mmapped_mem -= (size + p->prev_size);
1040
1041   ret = munmap((char *)p - p->prev_size, size + p->prev_size);
1042
1043   /* munmap returns non-zero on failure */
1044   assert(ret == 0);
1045 }
1046
1047 #if HAVE_MREMAP
1048
1049 #if __STD_C
1050 static mchunkptr mremap_chunk(mchunkptr p, size_t new_size)
1051 #else
1052 static mchunkptr mremap_chunk(p, new_size) mchunkptr p; size_t new_size;
1053 #endif
1054 {
1055   size_t page_mask = malloc_getpagesize - 1;
1056   INTERNAL_SIZE_T offset = p->prev_size;
1057   INTERNAL_SIZE_T size = chunksize(p);
1058   char *cp;
1059
1060   assert (chunk_is_mmapped(p));
1061   assert(! ((char*)p >= sbrk_base && (char*)p < sbrk_base + sbrked_mem));
1062   assert((n_mmaps > 0));
1063   assert(((size + offset) & (malloc_getpagesize-1)) == 0);
1064
1065   /* Note the extra SIZE_SZ overhead as in mmap_chunk(). */
1066   new_size = (new_size + offset + SIZE_SZ + page_mask) & ~page_mask;
1067
1068   cp = (char *)mremap((char *)p - offset, size + offset, new_size, 1);
1069
1070   if (cp == (char *)-1) return 0;
1071
1072   p = (mchunkptr)(cp + offset);
1073
1074   assert(aligned_OK(chunk2mem(p)));
1075
1076   assert((p->prev_size == offset));
1077   set_head(p, (new_size - offset)|IS_MMAPPED);
1078
1079   mmapped_mem -= size + offset;
1080   mmapped_mem += new_size;
1081   if ((unsigned long)mmapped_mem > (unsigned long)max_mmapped_mem)
1082     max_mmapped_mem = mmapped_mem;
1083   if ((unsigned long)(mmapped_mem + sbrked_mem) > (unsigned long)max_total_mem)
1084     max_total_mem = mmapped_mem + sbrked_mem;
1085   return p;
1086 }
1087
1088 #endif /* HAVE_MREMAP */
1089
1090 #endif /* HAVE_MMAP */
1091
1092 /*
1093   Extend the top-most chunk by obtaining memory from system.
1094   Main interface to sbrk (but see also malloc_trim).
1095 */
1096
1097 #if __STD_C
1098 static void malloc_extend_top(INTERNAL_SIZE_T nb)
1099 #else
1100 static void malloc_extend_top(nb) INTERNAL_SIZE_T nb;
1101 #endif
1102 {
1103   char*     brk;                  /* return value from sbrk */
1104   INTERNAL_SIZE_T front_misalign; /* unusable bytes at front of sbrked space */
1105   INTERNAL_SIZE_T correction;     /* bytes for 2nd sbrk call */
1106   char*     new_brk;              /* return of 2nd sbrk call */
1107   INTERNAL_SIZE_T top_size;       /* new size of top chunk */
1108
1109   mchunkptr old_top     = top;  /* Record state of old top */
1110   INTERNAL_SIZE_T old_top_size = chunksize(old_top);
1111   char*     old_end      = (char*)(chunk_at_offset(old_top, old_top_size));
1112
1113   /* Pad request with top_pad plus minimal overhead */
1114
1115   INTERNAL_SIZE_T    sbrk_size     = nb + top_pad + MINSIZE;
1116   unsigned long pagesz    = malloc_getpagesize;
1117
1118   /* If not the first time through, round to preserve page boundary */
1119   /* Otherwise, we need to correct to a page size below anyway. */
1120   /* (We also correct below if an intervening foreign sbrk call.) */
1121
1122   if (sbrk_base != (char*)(-1))
1123     sbrk_size = (sbrk_size + (pagesz - 1)) & ~(pagesz - 1);
1124
1125   brk = (char*)(MORECORE (sbrk_size));
1126
1127   /* Fail if sbrk failed or if a foreign sbrk call killed our space */
1128   if (brk == (char*)(MORECORE_FAILURE) ||
1129       (brk < old_end && old_top != initial_top))
1130     return;
1131
1132   sbrked_mem += sbrk_size;
1133
1134   if (brk == old_end) /* can just add bytes to current top */
1135   {
1136     top_size = sbrk_size + old_top_size;
1137     set_head(top, top_size | PREV_INUSE);
1138   }
1139   else
1140   {
1141     if (sbrk_base == (char*)(-1))  /* First time through. Record base */
1142       sbrk_base = brk;
1143     else  /* Someone else called sbrk().  Count those bytes as sbrked_mem. */
1144       sbrked_mem += brk - (char*)old_end;
1145
1146     /* Guarantee alignment of first new chunk made from this space */
1147     front_misalign = (unsigned long)chunk2mem(brk) & MALLOC_ALIGN_MASK;
1148     if (front_misalign > 0)
1149     {
1150       correction = (MALLOC_ALIGNMENT) - front_misalign;
1151       brk += correction;
1152     }
1153     else
1154       correction = 0;
1155
1156     /* Guarantee the next brk will be at a page boundary */
1157
1158     correction += ((((unsigned long)(brk + sbrk_size))+(pagesz-1)) &
1159                    ~(pagesz - 1)) - ((unsigned long)(brk + sbrk_size));
1160
1161     /* Allocate correction */
1162     new_brk = (char*)(MORECORE (correction));
1163     if (new_brk == (char*)(MORECORE_FAILURE)) return;
1164
1165     sbrked_mem += correction;
1166
1167     top = (mchunkptr)brk;
1168     top_size = new_brk - brk + correction;
1169     set_head(top, top_size | PREV_INUSE);
1170
1171     if (old_top != initial_top)
1172     {
1173
1174       /* There must have been an intervening foreign sbrk call. */
1175       /* A double fencepost is necessary to prevent consolidation */
1176
1177       /* If not enough space to do this, then user did something very wrong */
1178       if (old_top_size < MINSIZE)
1179       {
1180         set_head(top, PREV_INUSE); /* will force null return from malloc */
1181         return;
1182       }
1183
1184       /* Also keep size a multiple of MALLOC_ALIGNMENT */
1185       old_top_size = (old_top_size - 3*SIZE_SZ) & ~MALLOC_ALIGN_MASK;
1186       set_head_size(old_top, old_top_size);
1187       chunk_at_offset(old_top, old_top_size          )->size =
1188         SIZE_SZ|PREV_INUSE;
1189       chunk_at_offset(old_top, old_top_size + SIZE_SZ)->size =
1190         SIZE_SZ|PREV_INUSE;
1191       /* If possible, release the rest. */
1192       if (old_top_size >= MINSIZE)
1193         fREe(chunk2mem(old_top));
1194     }
1195   }
1196
1197   if ((unsigned long)sbrked_mem > (unsigned long)max_sbrked_mem)
1198     max_sbrked_mem = sbrked_mem;
1199   if ((unsigned long)(mmapped_mem + sbrked_mem) > (unsigned long)max_total_mem)
1200     max_total_mem = mmapped_mem + sbrked_mem;
1201
1202   /* We always land on a page boundary */
1203   assert(((unsigned long)((char*)top + top_size) & (pagesz - 1)) == 0);
1204 }
1205
1206
1207
1208
1209 /* Main public routines */
1210
1211
1212 /*
1213   Malloc Algorthim:
1214
1215     The requested size is first converted into a usable form, `nb'.
1216     This currently means to add 4 bytes overhead plus possibly more to
1217     obtain 8-byte alignment and/or to obtain a size of at least
1218     MINSIZE (currently 16 bytes), the smallest allocatable size.
1219     (All fits are considered `exact' if they are within MINSIZE bytes.)
1220
1221     From there, the first successful of the following steps is taken:
1222
1223       1. The bin corresponding to the request size is scanned, and if
1224          a chunk of exactly the right size is found, it is taken.
1225
1226       2. The most recently remaindered chunk is used if it is big
1227          enough.  This is a form of (roving) first fit, used only in
1228          the absence of exact fits. Runs of consecutive requests use
1229          the remainder of the chunk used for the previous such request
1230          whenever possible. This limited use of a first-fit style
1231          allocation strategy tends to give contiguous chunks
1232          coextensive lifetimes, which improves locality and can reduce
1233          fragmentation in the long run.
1234
1235       3. Other bins are scanned in increasing size order, using a
1236          chunk big enough to fulfill the request, and splitting off
1237          any remainder.  This search is strictly by best-fit; i.e.,
1238          the smallest (with ties going to approximately the least
1239          recently used) chunk that fits is selected.
1240
1241       4. If large enough, the chunk bordering the end of memory
1242          (`top') is split off. (This use of `top' is in accord with
1243          the best-fit search rule.  In effect, `top' is treated as
1244          larger (and thus less well fitting) than any other available
1245          chunk since it can be extended to be as large as necessary
1246          (up to system limitations).
1247
1248       5. If the request size meets the mmap threshold and the
1249          system supports mmap, and there are few enough currently
1250          allocated mmapped regions, and a call to mmap succeeds,
1251          the request is allocated via direct memory mapping.
1252
1253       6. Otherwise, the top of memory is extended by
1254          obtaining more space from the system (normally using sbrk,
1255          but definable to anything else via the MORECORE macro).
1256          Memory is gathered from the system (in system page-sized
1257          units) in a way that allows chunks obtained across different
1258          sbrk calls to be consolidated, but does not require
1259          contiguous memory. Thus, it should be safe to intersperse
1260          mallocs with other sbrk calls.
1261
1262
1263       All allocations are made from the the `lowest' part of any found
1264       chunk. (The implementation invariant is that prev_inuse is
1265       always true of any allocated chunk; i.e., that each allocated
1266       chunk borders either a previously allocated and still in-use chunk,
1267       or the base of its memory arena.)
1268
1269 */
1270
1271 #if __STD_C
1272 Void_t* mALLOc(size_t bytes)
1273 #else
1274 Void_t* mALLOc(bytes) size_t bytes;
1275 #endif
1276 {
1277   mchunkptr victim;                  /* inspected/selected chunk */
1278   INTERNAL_SIZE_T victim_size;       /* its size */
1279   int       idx;                     /* index for bin traversal */
1280   mbinptr   bin;                     /* associated bin */
1281   mchunkptr remainder;               /* remainder from a split */
1282   long      remainder_size;          /* its size */
1283   int       remainder_index;         /* its bin index */
1284   unsigned long block;               /* block traverser bit */
1285   int       startidx;                /* first bin of a traversed block */
1286   mchunkptr fwd;                     /* misc temp for linking */
1287   mchunkptr bck;                     /* misc temp for linking */
1288   mbinptr q;                         /* misc temp */
1289
1290   INTERNAL_SIZE_T nb;
1291
1292 #if CONFIG_VAL(SYS_MALLOC_F_LEN)
1293         if (!(gd->flags & GD_FLG_FULL_MALLOC_INIT))
1294                 return malloc_simple(bytes);
1295 #endif
1296
1297   /* check if mem_malloc_init() was run */
1298   if ((mem_malloc_start == 0) && (mem_malloc_end == 0)) {
1299     /* not initialized yet */
1300     return NULL;
1301   }
1302
1303   if ((long)bytes < 0) return NULL;
1304
1305   nb = request2size(bytes);  /* padded request size; */
1306
1307   /* Check for exact match in a bin */
1308
1309   if (is_small_request(nb))  /* Faster version for small requests */
1310   {
1311     idx = smallbin_index(nb);
1312
1313     /* No traversal or size check necessary for small bins.  */
1314
1315     q = bin_at(idx);
1316     victim = last(q);
1317
1318     /* Also scan the next one, since it would have a remainder < MINSIZE */
1319     if (victim == q)
1320     {
1321       q = next_bin(q);
1322       victim = last(q);
1323     }
1324     if (victim != q)
1325     {
1326       victim_size = chunksize(victim);
1327       unlink(victim, bck, fwd);
1328       set_inuse_bit_at_offset(victim, victim_size);
1329       check_malloced_chunk(victim, nb);
1330       return chunk2mem(victim);
1331     }
1332
1333     idx += 2; /* Set for bin scan below. We've already scanned 2 bins. */
1334
1335   }
1336   else
1337   {
1338     idx = bin_index(nb);
1339     bin = bin_at(idx);
1340
1341     for (victim = last(bin); victim != bin; victim = victim->bk)
1342     {
1343       victim_size = chunksize(victim);
1344       remainder_size = victim_size - nb;
1345
1346       if (remainder_size >= (long)MINSIZE) /* too big */
1347       {
1348         --idx; /* adjust to rescan below after checking last remainder */
1349         break;
1350       }
1351
1352       else if (remainder_size >= 0) /* exact fit */
1353       {
1354         unlink(victim, bck, fwd);
1355         set_inuse_bit_at_offset(victim, victim_size);
1356         check_malloced_chunk(victim, nb);
1357         return chunk2mem(victim);
1358       }
1359     }
1360
1361     ++idx;
1362
1363   }
1364
1365   /* Try to use the last split-off remainder */
1366
1367   if ( (victim = last_remainder->fd) != last_remainder)
1368   {
1369     victim_size = chunksize(victim);
1370     remainder_size = victim_size - nb;
1371
1372     if (remainder_size >= (long)MINSIZE) /* re-split */
1373     {
1374       remainder = chunk_at_offset(victim, nb);
1375       set_head(victim, nb | PREV_INUSE);
1376       link_last_remainder(remainder);
1377       set_head(remainder, remainder_size | PREV_INUSE);
1378       set_foot(remainder, remainder_size);
1379       check_malloced_chunk(victim, nb);
1380       return chunk2mem(victim);
1381     }
1382
1383     clear_last_remainder;
1384
1385     if (remainder_size >= 0)  /* exhaust */
1386     {
1387       set_inuse_bit_at_offset(victim, victim_size);
1388       check_malloced_chunk(victim, nb);
1389       return chunk2mem(victim);
1390     }
1391
1392     /* Else place in bin */
1393
1394     frontlink(victim, victim_size, remainder_index, bck, fwd);
1395   }
1396
1397   /*
1398      If there are any possibly nonempty big-enough blocks,
1399      search for best fitting chunk by scanning bins in blockwidth units.
1400   */
1401
1402   if ( (block = idx2binblock(idx)) <= binblocks_r)
1403   {
1404
1405     /* Get to the first marked block */
1406
1407     if ( (block & binblocks_r) == 0)
1408     {
1409       /* force to an even block boundary */
1410       idx = (idx & ~(BINBLOCKWIDTH - 1)) + BINBLOCKWIDTH;
1411       block <<= 1;
1412       while ((block & binblocks_r) == 0)
1413       {
1414         idx += BINBLOCKWIDTH;
1415         block <<= 1;
1416       }
1417     }
1418
1419     /* For each possibly nonempty block ... */
1420     for (;;)
1421     {
1422       startidx = idx;          /* (track incomplete blocks) */
1423       q = bin = bin_at(idx);
1424
1425       /* For each bin in this block ... */
1426       do
1427       {
1428         /* Find and use first big enough chunk ... */
1429
1430         for (victim = last(bin); victim != bin; victim = victim->bk)
1431         {
1432           victim_size = chunksize(victim);
1433           remainder_size = victim_size - nb;
1434
1435           if (remainder_size >= (long)MINSIZE) /* split */
1436           {
1437             remainder = chunk_at_offset(victim, nb);
1438             set_head(victim, nb | PREV_INUSE);
1439             unlink(victim, bck, fwd);
1440             link_last_remainder(remainder);
1441             set_head(remainder, remainder_size | PREV_INUSE);
1442             set_foot(remainder, remainder_size);
1443             check_malloced_chunk(victim, nb);
1444             return chunk2mem(victim);
1445           }
1446
1447           else if (remainder_size >= 0)  /* take */
1448           {
1449             set_inuse_bit_at_offset(victim, victim_size);
1450             unlink(victim, bck, fwd);
1451             check_malloced_chunk(victim, nb);
1452             return chunk2mem(victim);
1453           }
1454
1455         }
1456
1457        bin = next_bin(bin);
1458
1459       } while ((++idx & (BINBLOCKWIDTH - 1)) != 0);
1460
1461       /* Clear out the block bit. */
1462
1463       do   /* Possibly backtrack to try to clear a partial block */
1464       {
1465         if ((startidx & (BINBLOCKWIDTH - 1)) == 0)
1466         {
1467           av_[1] = (mbinptr)(binblocks_r & ~block);
1468           break;
1469         }
1470         --startidx;
1471        q = prev_bin(q);
1472       } while (first(q) == q);
1473
1474       /* Get to the next possibly nonempty block */
1475
1476       if ( (block <<= 1) <= binblocks_r && (block != 0) )
1477       {
1478         while ((block & binblocks_r) == 0)
1479         {
1480           idx += BINBLOCKWIDTH;
1481           block <<= 1;
1482         }
1483       }
1484       else
1485         break;
1486     }
1487   }
1488
1489
1490   /* Try to use top chunk */
1491
1492   /* Require that there be a remainder, ensuring top always exists  */
1493   if ( (remainder_size = chunksize(top) - nb) < (long)MINSIZE)
1494   {
1495
1496 #if HAVE_MMAP
1497     /* If big and would otherwise need to extend, try to use mmap instead */
1498     if ((unsigned long)nb >= (unsigned long)mmap_threshold &&
1499         (victim = mmap_chunk(nb)))
1500       return chunk2mem(victim);
1501 #endif
1502
1503     /* Try to extend */
1504     malloc_extend_top(nb);
1505     if ( (remainder_size = chunksize(top) - nb) < (long)MINSIZE)
1506       return NULL; /* propagate failure */
1507   }
1508
1509   victim = top;
1510   set_head(victim, nb | PREV_INUSE);
1511   top = chunk_at_offset(victim, nb);
1512   set_head(top, remainder_size | PREV_INUSE);
1513   check_malloced_chunk(victim, nb);
1514   return chunk2mem(victim);
1515
1516 }
1517
1518
1519
1520
1521 /*
1522
1523   free() algorithm :
1524
1525     cases:
1526
1527        1. free(0) has no effect.
1528
1529        2. If the chunk was allocated via mmap, it is release via munmap().
1530
1531        3. If a returned chunk borders the current high end of memory,
1532           it is consolidated into the top, and if the total unused
1533           topmost memory exceeds the trim threshold, malloc_trim is
1534           called.
1535
1536        4. Other chunks are consolidated as they arrive, and
1537           placed in corresponding bins. (This includes the case of
1538           consolidating with the current `last_remainder').
1539
1540 */
1541
1542
1543 #if __STD_C
1544 void fREe(Void_t* mem)
1545 #else
1546 void fREe(mem) Void_t* mem;
1547 #endif
1548 {
1549   mchunkptr p;         /* chunk corresponding to mem */
1550   INTERNAL_SIZE_T hd;  /* its head field */
1551   INTERNAL_SIZE_T sz;  /* its size */
1552   int       idx;       /* its bin index */
1553   mchunkptr next;      /* next contiguous chunk */
1554   INTERNAL_SIZE_T nextsz; /* its size */
1555   INTERNAL_SIZE_T prevsz; /* size of previous contiguous chunk */
1556   mchunkptr bck;       /* misc temp for linking */
1557   mchunkptr fwd;       /* misc temp for linking */
1558   int       islr;      /* track whether merging with last_remainder */
1559
1560 #if CONFIG_VAL(SYS_MALLOC_F_LEN)
1561         /* free() is a no-op - all the memory will be freed on relocation */
1562         if (!(gd->flags & GD_FLG_FULL_MALLOC_INIT))
1563                 return;
1564 #endif
1565
1566   if (mem == NULL)                              /* free(0) has no effect */
1567     return;
1568
1569   p = mem2chunk(mem);
1570   hd = p->size;
1571
1572 #if HAVE_MMAP
1573   if (hd & IS_MMAPPED)                       /* release mmapped memory. */
1574   {
1575     munmap_chunk(p);
1576     return;
1577   }
1578 #endif
1579
1580   check_inuse_chunk(p);
1581
1582   sz = hd & ~PREV_INUSE;
1583   next = chunk_at_offset(p, sz);
1584   nextsz = chunksize(next);
1585
1586   if (next == top)                            /* merge with top */
1587   {
1588     sz += nextsz;
1589
1590     if (!(hd & PREV_INUSE))                    /* consolidate backward */
1591     {
1592       prevsz = p->prev_size;
1593       p = chunk_at_offset(p, -((long) prevsz));
1594       sz += prevsz;
1595       unlink(p, bck, fwd);
1596     }
1597
1598     set_head(p, sz | PREV_INUSE);
1599     top = p;
1600     if ((unsigned long)(sz) >= (unsigned long)trim_threshold)
1601       malloc_trim(top_pad);
1602     return;
1603   }
1604
1605   set_head(next, nextsz);                    /* clear inuse bit */
1606
1607   islr = 0;
1608
1609   if (!(hd & PREV_INUSE))                    /* consolidate backward */
1610   {
1611     prevsz = p->prev_size;
1612     p = chunk_at_offset(p, -((long) prevsz));
1613     sz += prevsz;
1614
1615     if (p->fd == last_remainder)             /* keep as last_remainder */
1616       islr = 1;
1617     else
1618       unlink(p, bck, fwd);
1619   }
1620
1621   if (!(inuse_bit_at_offset(next, nextsz)))   /* consolidate forward */
1622   {
1623     sz += nextsz;
1624
1625     if (!islr && next->fd == last_remainder)  /* re-insert last_remainder */
1626     {
1627       islr = 1;
1628       link_last_remainder(p);
1629     }
1630     else
1631       unlink(next, bck, fwd);
1632   }
1633
1634
1635   set_head(p, sz | PREV_INUSE);
1636   set_foot(p, sz);
1637   if (!islr)
1638     frontlink(p, sz, idx, bck, fwd);
1639 }
1640
1641
1642
1643
1644
1645 /*
1646
1647   Realloc algorithm:
1648
1649     Chunks that were obtained via mmap cannot be extended or shrunk
1650     unless HAVE_MREMAP is defined, in which case mremap is used.
1651     Otherwise, if their reallocation is for additional space, they are
1652     copied.  If for less, they are just left alone.
1653
1654     Otherwise, if the reallocation is for additional space, and the
1655     chunk can be extended, it is, else a malloc-copy-free sequence is
1656     taken.  There are several different ways that a chunk could be
1657     extended. All are tried:
1658
1659        * Extending forward into following adjacent free chunk.
1660        * Shifting backwards, joining preceding adjacent space
1661        * Both shifting backwards and extending forward.
1662        * Extending into newly sbrked space
1663
1664     Unless the #define REALLOC_ZERO_BYTES_FREES is set, realloc with a
1665     size argument of zero (re)allocates a minimum-sized chunk.
1666
1667     If the reallocation is for less space, and the new request is for
1668     a `small' (<512 bytes) size, then the newly unused space is lopped
1669     off and freed.
1670
1671     The old unix realloc convention of allowing the last-free'd chunk
1672     to be used as an argument to realloc is no longer supported.
1673     I don't know of any programs still relying on this feature,
1674     and allowing it would also allow too many other incorrect
1675     usages of realloc to be sensible.
1676
1677
1678 */
1679
1680
1681 #if __STD_C
1682 Void_t* rEALLOc(Void_t* oldmem, size_t bytes)
1683 #else
1684 Void_t* rEALLOc(oldmem, bytes) Void_t* oldmem; size_t bytes;
1685 #endif
1686 {
1687   INTERNAL_SIZE_T    nb;      /* padded request size */
1688
1689   mchunkptr oldp;             /* chunk corresponding to oldmem */
1690   INTERNAL_SIZE_T    oldsize; /* its size */
1691
1692   mchunkptr newp;             /* chunk to return */
1693   INTERNAL_SIZE_T    newsize; /* its size */
1694   Void_t*   newmem;           /* corresponding user mem */
1695
1696   mchunkptr next;             /* next contiguous chunk after oldp */
1697   INTERNAL_SIZE_T  nextsize;  /* its size */
1698
1699   mchunkptr prev;             /* previous contiguous chunk before oldp */
1700   INTERNAL_SIZE_T  prevsize;  /* its size */
1701
1702   mchunkptr remainder;        /* holds split off extra space from newp */
1703   INTERNAL_SIZE_T  remainder_size;   /* its size */
1704
1705   mchunkptr bck;              /* misc temp for linking */
1706   mchunkptr fwd;              /* misc temp for linking */
1707
1708 #ifdef REALLOC_ZERO_BYTES_FREES
1709   if (!bytes) {
1710         fREe(oldmem);
1711         return NULL;
1712   }
1713 #endif
1714
1715   if ((long)bytes < 0) return NULL;
1716
1717   /* realloc of null is supposed to be same as malloc */
1718   if (oldmem == NULL) return mALLOc(bytes);
1719
1720 #if CONFIG_VAL(SYS_MALLOC_F_LEN)
1721         if (!(gd->flags & GD_FLG_FULL_MALLOC_INIT)) {
1722                 /* This is harder to support and should not be needed */
1723                 panic("pre-reloc realloc() is not supported");
1724         }
1725 #endif
1726
1727   newp    = oldp    = mem2chunk(oldmem);
1728   newsize = oldsize = chunksize(oldp);
1729
1730
1731   nb = request2size(bytes);
1732
1733 #if HAVE_MMAP
1734   if (chunk_is_mmapped(oldp))
1735   {
1736 #if HAVE_MREMAP
1737     newp = mremap_chunk(oldp, nb);
1738     if(newp) return chunk2mem(newp);
1739 #endif
1740     /* Note the extra SIZE_SZ overhead. */
1741     if(oldsize - SIZE_SZ >= nb) return oldmem; /* do nothing */
1742     /* Must alloc, copy, free. */
1743     newmem = mALLOc(bytes);
1744     if (!newmem)
1745         return NULL; /* propagate failure */
1746     MALLOC_COPY(newmem, oldmem, oldsize - 2*SIZE_SZ);
1747     munmap_chunk(oldp);
1748     return newmem;
1749   }
1750 #endif
1751
1752   check_inuse_chunk(oldp);
1753
1754   if ((long)(oldsize) < (long)(nb))
1755   {
1756
1757     /* Try expanding forward */
1758
1759     next = chunk_at_offset(oldp, oldsize);
1760     if (next == top || !inuse(next))
1761     {
1762       nextsize = chunksize(next);
1763
1764       /* Forward into top only if a remainder */
1765       if (next == top)
1766       {
1767         if ((long)(nextsize + newsize) >= (long)(nb + MINSIZE))
1768         {
1769           newsize += nextsize;
1770           top = chunk_at_offset(oldp, nb);
1771           set_head(top, (newsize - nb) | PREV_INUSE);
1772           set_head_size(oldp, nb);
1773           return chunk2mem(oldp);
1774         }
1775       }
1776
1777       /* Forward into next chunk */
1778       else if (((long)(nextsize + newsize) >= (long)(nb)))
1779       {
1780         unlink(next, bck, fwd);
1781         newsize  += nextsize;
1782         goto split;
1783       }
1784     }
1785     else
1786     {
1787       next = NULL;
1788       nextsize = 0;
1789     }
1790
1791     /* Try shifting backwards. */
1792
1793     if (!prev_inuse(oldp))
1794     {
1795       prev = prev_chunk(oldp);
1796       prevsize = chunksize(prev);
1797
1798       /* try forward + backward first to save a later consolidation */
1799
1800       if (next != NULL)
1801       {
1802         /* into top */
1803         if (next == top)
1804         {
1805           if ((long)(nextsize + prevsize + newsize) >= (long)(nb + MINSIZE))
1806           {
1807             unlink(prev, bck, fwd);
1808             newp = prev;
1809             newsize += prevsize + nextsize;
1810             newmem = chunk2mem(newp);
1811             MALLOC_COPY(newmem, oldmem, oldsize - SIZE_SZ);
1812             top = chunk_at_offset(newp, nb);
1813             set_head(top, (newsize - nb) | PREV_INUSE);
1814             set_head_size(newp, nb);
1815             return newmem;
1816           }
1817         }
1818
1819         /* into next chunk */
1820         else if (((long)(nextsize + prevsize + newsize) >= (long)(nb)))
1821         {
1822           unlink(next, bck, fwd);
1823           unlink(prev, bck, fwd);
1824           newp = prev;
1825           newsize += nextsize + prevsize;
1826           newmem = chunk2mem(newp);
1827           MALLOC_COPY(newmem, oldmem, oldsize - SIZE_SZ);
1828           goto split;
1829         }
1830       }
1831
1832       /* backward only */
1833       if (prev != NULL && (long)(prevsize + newsize) >= (long)nb)
1834       {
1835         unlink(prev, bck, fwd);
1836         newp = prev;
1837         newsize += prevsize;
1838         newmem = chunk2mem(newp);
1839         MALLOC_COPY(newmem, oldmem, oldsize - SIZE_SZ);
1840         goto split;
1841       }
1842     }
1843
1844     /* Must allocate */
1845
1846     newmem = mALLOc (bytes);
1847
1848     if (newmem == NULL)  /* propagate failure */
1849       return NULL;
1850
1851     /* Avoid copy if newp is next chunk after oldp. */
1852     /* (This can only happen when new chunk is sbrk'ed.) */
1853
1854     if ( (newp = mem2chunk(newmem)) == next_chunk(oldp))
1855     {
1856       newsize += chunksize(newp);
1857       newp = oldp;
1858       goto split;
1859     }
1860
1861     /* Otherwise copy, free, and exit */
1862     MALLOC_COPY(newmem, oldmem, oldsize - SIZE_SZ);
1863     fREe(oldmem);
1864     return newmem;
1865   }
1866
1867
1868  split:  /* split off extra room in old or expanded chunk */
1869
1870   if (newsize - nb >= MINSIZE) /* split off remainder */
1871   {
1872     remainder = chunk_at_offset(newp, nb);
1873     remainder_size = newsize - nb;
1874     set_head_size(newp, nb);
1875     set_head(remainder, remainder_size | PREV_INUSE);
1876     set_inuse_bit_at_offset(remainder, remainder_size);
1877     fREe(chunk2mem(remainder)); /* let free() deal with it */
1878   }
1879   else
1880   {
1881     set_head_size(newp, newsize);
1882     set_inuse_bit_at_offset(newp, newsize);
1883   }
1884
1885   check_inuse_chunk(newp);
1886   return chunk2mem(newp);
1887 }
1888
1889
1890
1891
1892 /*
1893
1894   memalign algorithm:
1895
1896     memalign requests more than enough space from malloc, finds a spot
1897     within that chunk that meets the alignment request, and then
1898     possibly frees the leading and trailing space.
1899
1900     The alignment argument must be a power of two. This property is not
1901     checked by memalign, so misuse may result in random runtime errors.
1902
1903     8-byte alignment is guaranteed by normal malloc calls, so don't
1904     bother calling memalign with an argument of 8 or less.
1905
1906     Overreliance on memalign is a sure way to fragment space.
1907
1908 */
1909
1910
1911 #if __STD_C
1912 Void_t* mEMALIGn(size_t alignment, size_t bytes)
1913 #else
1914 Void_t* mEMALIGn(alignment, bytes) size_t alignment; size_t bytes;
1915 #endif
1916 {
1917   INTERNAL_SIZE_T    nb;      /* padded  request size */
1918   char*     m;                /* memory returned by malloc call */
1919   mchunkptr p;                /* corresponding chunk */
1920   char*     brk;              /* alignment point within p */
1921   mchunkptr newp;             /* chunk to return */
1922   INTERNAL_SIZE_T  newsize;   /* its size */
1923   INTERNAL_SIZE_T  leadsize;  /* leading space befor alignment point */
1924   mchunkptr remainder;        /* spare room at end to split off */
1925   long      remainder_size;   /* its size */
1926
1927   if ((long)bytes < 0) return NULL;
1928
1929 #if CONFIG_VAL(SYS_MALLOC_F_LEN)
1930         if (!(gd->flags & GD_FLG_FULL_MALLOC_INIT)) {
1931                 return memalign_simple(alignment, bytes);
1932         }
1933 #endif
1934
1935   /* If need less alignment than we give anyway, just relay to malloc */
1936
1937   if (alignment <= MALLOC_ALIGNMENT) return mALLOc(bytes);
1938
1939   /* Otherwise, ensure that it is at least a minimum chunk size */
1940
1941   if (alignment <  MINSIZE) alignment = MINSIZE;
1942
1943   /* Call malloc with worst case padding to hit alignment. */
1944
1945   nb = request2size(bytes);
1946   m  = (char*)(mALLOc(nb + alignment + MINSIZE));
1947
1948   /*
1949   * The attempt to over-allocate (with a size large enough to guarantee the
1950   * ability to find an aligned region within allocated memory) failed.
1951   *
1952   * Try again, this time only allocating exactly the size the user wants. If
1953   * the allocation now succeeds and just happens to be aligned, we can still
1954   * fulfill the user's request.
1955   */
1956   if (m == NULL) {
1957     size_t extra, extra2;
1958     /*
1959      * Use bytes not nb, since mALLOc internally calls request2size too, and
1960      * each call increases the size to allocate, to account for the header.
1961      */
1962     m  = (char*)(mALLOc(bytes));
1963     /* Aligned -> return it */
1964     if ((((unsigned long)(m)) % alignment) == 0)
1965       return m;
1966     /*
1967      * Otherwise, try again, requesting enough extra space to be able to
1968      * acquire alignment.
1969      */
1970     fREe(m);
1971     /* Add in extra bytes to match misalignment of unexpanded allocation */
1972     extra = alignment - (((unsigned long)(m)) % alignment);
1973     m  = (char*)(mALLOc(bytes + extra));
1974     /*
1975      * m might not be the same as before. Validate that the previous value of
1976      * extra still works for the current value of m.
1977      * If (!m), extra2=alignment so 
1978      */
1979     if (m) {
1980       extra2 = alignment - (((unsigned long)(m)) % alignment);
1981       if (extra2 > extra) {
1982         fREe(m);
1983         m = NULL;
1984       }
1985     }
1986     /* Fall through to original NULL check and chunk splitting logic */
1987   }
1988
1989   if (m == NULL) return NULL; /* propagate failure */
1990
1991   p = mem2chunk(m);
1992
1993   if ((((unsigned long)(m)) % alignment) == 0) /* aligned */
1994   {
1995 #if HAVE_MMAP
1996     if(chunk_is_mmapped(p))
1997       return chunk2mem(p); /* nothing more to do */
1998 #endif
1999   }
2000   else /* misaligned */
2001   {
2002     /*
2003       Find an aligned spot inside chunk.
2004       Since we need to give back leading space in a chunk of at
2005       least MINSIZE, if the first calculation places us at
2006       a spot with less than MINSIZE leader, we can move to the
2007       next aligned spot -- we've allocated enough total room so that
2008       this is always possible.
2009     */
2010
2011     brk = (char*)mem2chunk(((unsigned long)(m + alignment - 1)) & -((signed) alignment));
2012     if ((long)(brk - (char*)(p)) < MINSIZE) brk = brk + alignment;
2013
2014     newp = (mchunkptr)brk;
2015     leadsize = brk - (char*)(p);
2016     newsize = chunksize(p) - leadsize;
2017
2018 #if HAVE_MMAP
2019     if(chunk_is_mmapped(p))
2020     {
2021       newp->prev_size = p->prev_size + leadsize;
2022       set_head(newp, newsize|IS_MMAPPED);
2023       return chunk2mem(newp);
2024     }
2025 #endif
2026
2027     /* give back leader, use the rest */
2028
2029     set_head(newp, newsize | PREV_INUSE);
2030     set_inuse_bit_at_offset(newp, newsize);
2031     set_head_size(p, leadsize);
2032     fREe(chunk2mem(p));
2033     p = newp;
2034
2035     assert (newsize >= nb && (((unsigned long)(chunk2mem(p))) % alignment) == 0);
2036   }
2037
2038   /* Also give back spare room at the end */
2039
2040   remainder_size = chunksize(p) - nb;
2041
2042   if (remainder_size >= (long)MINSIZE)
2043   {
2044     remainder = chunk_at_offset(p, nb);
2045     set_head(remainder, remainder_size | PREV_INUSE);
2046     set_head_size(p, nb);
2047     fREe(chunk2mem(remainder));
2048   }
2049
2050   check_inuse_chunk(p);
2051   return chunk2mem(p);
2052
2053 }
2054
2055
2056
2057
2058 /*
2059     valloc just invokes memalign with alignment argument equal
2060     to the page size of the system (or as near to this as can
2061     be figured out from all the includes/defines above.)
2062 */
2063
2064 #if __STD_C
2065 Void_t* vALLOc(size_t bytes)
2066 #else
2067 Void_t* vALLOc(bytes) size_t bytes;
2068 #endif
2069 {
2070   return mEMALIGn (malloc_getpagesize, bytes);
2071 }
2072
2073 /*
2074   pvalloc just invokes valloc for the nearest pagesize
2075   that will accommodate request
2076 */
2077
2078
2079 #if __STD_C
2080 Void_t* pvALLOc(size_t bytes)
2081 #else
2082 Void_t* pvALLOc(bytes) size_t bytes;
2083 #endif
2084 {
2085   size_t pagesize = malloc_getpagesize;
2086   return mEMALIGn (pagesize, (bytes + pagesize - 1) & ~(pagesize - 1));
2087 }
2088
2089 /*
2090
2091   calloc calls malloc, then zeroes out the allocated chunk.
2092
2093 */
2094
2095 #if __STD_C
2096 Void_t* cALLOc(size_t n, size_t elem_size)
2097 #else
2098 Void_t* cALLOc(n, elem_size) size_t n; size_t elem_size;
2099 #endif
2100 {
2101   mchunkptr p;
2102   INTERNAL_SIZE_T csz;
2103
2104   INTERNAL_SIZE_T sz = n * elem_size;
2105
2106
2107   /* check if expand_top called, in which case don't need to clear */
2108 #ifdef CONFIG_SYS_MALLOC_CLEAR_ON_INIT
2109 #if MORECORE_CLEARS
2110   mchunkptr oldtop = top;
2111   INTERNAL_SIZE_T oldtopsize = chunksize(top);
2112 #endif
2113 #endif
2114   Void_t* mem = mALLOc (sz);
2115
2116   if ((long)n < 0) return NULL;
2117
2118   if (mem == NULL)
2119     return NULL;
2120   else
2121   {
2122 #if CONFIG_VAL(SYS_MALLOC_F_LEN)
2123         if (!(gd->flags & GD_FLG_FULL_MALLOC_INIT)) {
2124                 memset(mem, 0, sz);
2125                 return mem;
2126         }
2127 #endif
2128     p = mem2chunk(mem);
2129
2130     /* Two optional cases in which clearing not necessary */
2131
2132
2133 #if HAVE_MMAP
2134     if (chunk_is_mmapped(p)) return mem;
2135 #endif
2136
2137     csz = chunksize(p);
2138
2139 #ifdef CONFIG_SYS_MALLOC_CLEAR_ON_INIT
2140 #if MORECORE_CLEARS
2141     if (p == oldtop && csz > oldtopsize)
2142     {
2143       /* clear only the bytes from non-freshly-sbrked memory */
2144       csz = oldtopsize;
2145     }
2146 #endif
2147 #endif
2148
2149     MALLOC_ZERO(mem, csz - SIZE_SZ);
2150     return mem;
2151   }
2152 }
2153
2154 /*
2155
2156   cfree just calls free. It is needed/defined on some systems
2157   that pair it with calloc, presumably for odd historical reasons.
2158
2159 */
2160
2161 #if !defined(INTERNAL_LINUX_C_LIB) || !defined(__ELF__)
2162 #if __STD_C
2163 void cfree(Void_t *mem)
2164 #else
2165 void cfree(mem) Void_t *mem;
2166 #endif
2167 {
2168   fREe(mem);
2169 }
2170 #endif
2171
2172
2173
2174 /*
2175
2176     Malloc_trim gives memory back to the system (via negative
2177     arguments to sbrk) if there is unused memory at the `high' end of
2178     the malloc pool. You can call this after freeing large blocks of
2179     memory to potentially reduce the system-level memory requirements
2180     of a program. However, it cannot guarantee to reduce memory. Under
2181     some allocation patterns, some large free blocks of memory will be
2182     locked between two used chunks, so they cannot be given back to
2183     the system.
2184
2185     The `pad' argument to malloc_trim represents the amount of free
2186     trailing space to leave untrimmed. If this argument is zero,
2187     only the minimum amount of memory to maintain internal data
2188     structures will be left (one page or less). Non-zero arguments
2189     can be supplied to maintain enough trailing space to service
2190     future expected allocations without having to re-obtain memory
2191     from the system.
2192
2193     Malloc_trim returns 1 if it actually released any memory, else 0.
2194
2195 */
2196
2197 #if __STD_C
2198 int malloc_trim(size_t pad)
2199 #else
2200 int malloc_trim(pad) size_t pad;
2201 #endif
2202 {
2203   long  top_size;        /* Amount of top-most memory */
2204   long  extra;           /* Amount to release */
2205   char* current_brk;     /* address returned by pre-check sbrk call */
2206   char* new_brk;         /* address returned by negative sbrk call */
2207
2208   unsigned long pagesz = malloc_getpagesize;
2209
2210   top_size = chunksize(top);
2211   extra = ((top_size - pad - MINSIZE + (pagesz-1)) / pagesz - 1) * pagesz;
2212
2213   if (extra < (long)pagesz)  /* Not enough memory to release */
2214     return 0;
2215
2216   else
2217   {
2218     /* Test to make sure no one else called sbrk */
2219     current_brk = (char*)(MORECORE (0));
2220     if (current_brk != (char*)(top) + top_size)
2221       return 0;     /* Apparently we don't own memory; must fail */
2222
2223     else
2224     {
2225       new_brk = (char*)(MORECORE (-extra));
2226
2227       if (new_brk == (char*)(MORECORE_FAILURE)) /* sbrk failed? */
2228       {
2229         /* Try to figure out what we have */
2230         current_brk = (char*)(MORECORE (0));
2231         top_size = current_brk - (char*)top;
2232         if (top_size >= (long)MINSIZE) /* if not, we are very very dead! */
2233         {
2234           sbrked_mem = current_brk - sbrk_base;
2235           set_head(top, top_size | PREV_INUSE);
2236         }
2237         check_chunk(top);
2238         return 0;
2239       }
2240
2241       else
2242       {
2243         /* Success. Adjust top accordingly. */
2244         set_head(top, (top_size - extra) | PREV_INUSE);
2245         sbrked_mem -= extra;
2246         check_chunk(top);
2247         return 1;
2248       }
2249     }
2250   }
2251 }
2252
2253
2254
2255 /*
2256   malloc_usable_size:
2257
2258     This routine tells you how many bytes you can actually use in an
2259     allocated chunk, which may be more than you requested (although
2260     often not). You can use this many bytes without worrying about
2261     overwriting other allocated objects. Not a particularly great
2262     programming practice, but still sometimes useful.
2263
2264 */
2265
2266 #if __STD_C
2267 size_t malloc_usable_size(Void_t* mem)
2268 #else
2269 size_t malloc_usable_size(mem) Void_t* mem;
2270 #endif
2271 {
2272   mchunkptr p;
2273   if (mem == NULL)
2274     return 0;
2275   else
2276   {
2277     p = mem2chunk(mem);
2278     if(!chunk_is_mmapped(p))
2279     {
2280       if (!inuse(p)) return 0;
2281       check_inuse_chunk(p);
2282       return chunksize(p) - SIZE_SZ;
2283     }
2284     return chunksize(p) - 2*SIZE_SZ;
2285   }
2286 }
2287
2288
2289
2290
2291 /* Utility to update current_mallinfo for malloc_stats and mallinfo() */
2292
2293 #ifdef DEBUG
2294 static void malloc_update_mallinfo()
2295 {
2296   int i;
2297   mbinptr b;
2298   mchunkptr p;
2299 #ifdef DEBUG
2300   mchunkptr q;
2301 #endif
2302
2303   INTERNAL_SIZE_T avail = chunksize(top);
2304   int   navail = ((long)(avail) >= (long)MINSIZE)? 1 : 0;
2305
2306   for (i = 1; i < NAV; ++i)
2307   {
2308     b = bin_at(i);
2309     for (p = last(b); p != b; p = p->bk)
2310     {
2311 #ifdef DEBUG
2312       check_free_chunk(p);
2313       for (q = next_chunk(p);
2314            q < top && inuse(q) && (long)(chunksize(q)) >= (long)MINSIZE;
2315            q = next_chunk(q))
2316         check_inuse_chunk(q);
2317 #endif
2318       avail += chunksize(p);
2319       navail++;
2320     }
2321   }
2322
2323   current_mallinfo.ordblks = navail;
2324   current_mallinfo.uordblks = sbrked_mem - avail;
2325   current_mallinfo.fordblks = avail;
2326   current_mallinfo.hblks = n_mmaps;
2327   current_mallinfo.hblkhd = mmapped_mem;
2328   current_mallinfo.keepcost = chunksize(top);
2329
2330 }
2331 #endif  /* DEBUG */
2332
2333
2334
2335 /*
2336
2337   malloc_stats:
2338
2339     Prints on the amount of space obtain from the system (both
2340     via sbrk and mmap), the maximum amount (which may be more than
2341     current if malloc_trim and/or munmap got called), the maximum
2342     number of simultaneous mmap regions used, and the current number
2343     of bytes allocated via malloc (or realloc, etc) but not yet
2344     freed. (Note that this is the number of bytes allocated, not the
2345     number requested. It will be larger than the number requested
2346     because of alignment and bookkeeping overhead.)
2347
2348 */
2349
2350 #ifdef DEBUG
2351 void malloc_stats()
2352 {
2353   malloc_update_mallinfo();
2354   printf("max system bytes = %10u\n",
2355           (unsigned int)(max_total_mem));
2356   printf("system bytes     = %10u\n",
2357           (unsigned int)(sbrked_mem + mmapped_mem));
2358   printf("in use bytes     = %10u\n",
2359           (unsigned int)(current_mallinfo.uordblks + mmapped_mem));
2360 #if HAVE_MMAP
2361   printf("max mmap regions = %10u\n",
2362           (unsigned int)max_n_mmaps);
2363 #endif
2364 }
2365 #endif  /* DEBUG */
2366
2367 /*
2368   mallinfo returns a copy of updated current mallinfo.
2369 */
2370
2371 #ifdef DEBUG
2372 struct mallinfo mALLINFo()
2373 {
2374   malloc_update_mallinfo();
2375   return current_mallinfo;
2376 }
2377 #endif  /* DEBUG */
2378
2379
2380
2381
2382 /*
2383   mallopt:
2384
2385     mallopt is the general SVID/XPG interface to tunable parameters.
2386     The format is to provide a (parameter-number, parameter-value) pair.
2387     mallopt then sets the corresponding parameter to the argument
2388     value if it can (i.e., so long as the value is meaningful),
2389     and returns 1 if successful else 0.
2390
2391     See descriptions of tunable parameters above.
2392
2393 */
2394
2395 #if __STD_C
2396 int mALLOPt(int param_number, int value)
2397 #else
2398 int mALLOPt(param_number, value) int param_number; int value;
2399 #endif
2400 {
2401   switch(param_number)
2402   {
2403     case M_TRIM_THRESHOLD:
2404       trim_threshold = value; return 1;
2405     case M_TOP_PAD:
2406       top_pad = value; return 1;
2407     case M_MMAP_THRESHOLD:
2408       mmap_threshold = value; return 1;
2409     case M_MMAP_MAX:
2410 #if HAVE_MMAP
2411       n_mmaps_max = value; return 1;
2412 #else
2413       if (value != 0) return 0; else  n_mmaps_max = value; return 1;
2414 #endif
2415
2416     default:
2417       return 0;
2418   }
2419 }
2420
2421 int initf_malloc(void)
2422 {
2423 #if CONFIG_VAL(SYS_MALLOC_F_LEN)
2424         assert(gd->malloc_base);        /* Set up by crt0.S */
2425         gd->malloc_limit = CONFIG_VAL(SYS_MALLOC_F_LEN);
2426         gd->malloc_ptr = 0;
2427 #endif
2428
2429         return 0;
2430 }
2431
2432 /*
2433
2434 History:
2435
2436     V2.6.6 Sun Dec  5 07:42:19 1999  Doug Lea  (dl at gee)
2437       * return null for negative arguments
2438       * Added Several WIN32 cleanups from Martin C. Fong <mcfong@yahoo.com>
2439          * Add 'LACKS_SYS_PARAM_H' for those systems without 'sys/param.h'
2440           (e.g. WIN32 platforms)
2441          * Cleanup up header file inclusion for WIN32 platforms
2442          * Cleanup code to avoid Microsoft Visual C++ compiler complaints
2443          * Add 'USE_DL_PREFIX' to quickly allow co-existence with existing
2444            memory allocation routines
2445          * Set 'malloc_getpagesize' for WIN32 platforms (needs more work)
2446          * Use 'assert' rather than 'ASSERT' in WIN32 code to conform to
2447            usage of 'assert' in non-WIN32 code
2448          * Improve WIN32 'sbrk()' emulation's 'findRegion()' routine to
2449            avoid infinite loop
2450       * Always call 'fREe()' rather than 'free()'
2451
2452     V2.6.5 Wed Jun 17 15:57:31 1998  Doug Lea  (dl at gee)
2453       * Fixed ordering problem with boundary-stamping
2454
2455     V2.6.3 Sun May 19 08:17:58 1996  Doug Lea  (dl at gee)
2456       * Added pvalloc, as recommended by H.J. Liu
2457       * Added 64bit pointer support mainly from Wolfram Gloger
2458       * Added anonymously donated WIN32 sbrk emulation
2459       * Malloc, calloc, getpagesize: add optimizations from Raymond Nijssen
2460       * malloc_extend_top: fix mask error that caused wastage after
2461         foreign sbrks
2462       * Add linux mremap support code from HJ Liu
2463
2464     V2.6.2 Tue Dec  5 06:52:55 1995  Doug Lea  (dl at gee)
2465       * Integrated most documentation with the code.
2466       * Add support for mmap, with help from
2467         Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
2468       * Use last_remainder in more cases.
2469       * Pack bins using idea from  colin@nyx10.cs.du.edu
2470       * Use ordered bins instead of best-fit threshhold
2471       * Eliminate block-local decls to simplify tracing and debugging.
2472       * Support another case of realloc via move into top
2473       * Fix error occuring when initial sbrk_base not word-aligned.
2474       * Rely on page size for units instead of SBRK_UNIT to
2475         avoid surprises about sbrk alignment conventions.
2476       * Add mallinfo, mallopt. Thanks to Raymond Nijssen
2477         (raymond@es.ele.tue.nl) for the suggestion.
2478       * Add `pad' argument to malloc_trim and top_pad mallopt parameter.
2479       * More precautions for cases where other routines call sbrk,
2480         courtesy of Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
2481       * Added macros etc., allowing use in linux libc from
2482         H.J. Lu (hjl@gnu.ai.mit.edu)
2483       * Inverted this history list
2484
2485     V2.6.1 Sat Dec  2 14:10:57 1995  Doug Lea  (dl at gee)
2486       * Re-tuned and fixed to behave more nicely with V2.6.0 changes.
2487       * Removed all preallocation code since under current scheme
2488         the work required to undo bad preallocations exceeds
2489         the work saved in good cases for most test programs.
2490       * No longer use return list or unconsolidated bins since
2491         no scheme using them consistently outperforms those that don't
2492         given above changes.
2493       * Use best fit for very large chunks to prevent some worst-cases.
2494       * Added some support for debugging
2495
2496     V2.6.0 Sat Nov  4 07:05:23 1995  Doug Lea  (dl at gee)
2497       * Removed footers when chunks are in use. Thanks to
2498         Paul Wilson (wilson@cs.texas.edu) for the suggestion.
2499
2500     V2.5.4 Wed Nov  1 07:54:51 1995  Doug Lea  (dl at gee)
2501       * Added malloc_trim, with help from Wolfram Gloger
2502         (wmglo@Dent.MED.Uni-Muenchen.DE).
2503
2504     V2.5.3 Tue Apr 26 10:16:01 1994  Doug Lea  (dl at g)
2505
2506     V2.5.2 Tue Apr  5 16:20:40 1994  Doug Lea  (dl at g)
2507       * realloc: try to expand in both directions
2508       * malloc: swap order of clean-bin strategy;
2509       * realloc: only conditionally expand backwards
2510       * Try not to scavenge used bins
2511       * Use bin counts as a guide to preallocation
2512       * Occasionally bin return list chunks in first scan
2513       * Add a few optimizations from colin@nyx10.cs.du.edu
2514
2515     V2.5.1 Sat Aug 14 15:40:43 1993  Doug Lea  (dl at g)
2516       * faster bin computation & slightly different binning
2517       * merged all consolidations to one part of malloc proper
2518          (eliminating old malloc_find_space & malloc_clean_bin)
2519       * Scan 2 returns chunks (not just 1)
2520       * Propagate failure in realloc if malloc returns 0
2521       * Add stuff to allow compilation on non-ANSI compilers
2522           from kpv@research.att.com
2523
2524     V2.5 Sat Aug  7 07:41:59 1993  Doug Lea  (dl at g.oswego.edu)
2525       * removed potential for odd address access in prev_chunk
2526       * removed dependency on getpagesize.h
2527       * misc cosmetics and a bit more internal documentation
2528       * anticosmetics: mangled names in macros to evade debugger strangeness
2529       * tested on sparc, hp-700, dec-mips, rs6000
2530           with gcc & native cc (hp, dec only) allowing
2531           Detlefs & Zorn comparison study (in SIGPLAN Notices.)
2532
2533     Trial version Fri Aug 28 13:14:29 1992  Doug Lea  (dl at g.oswego.edu)
2534       * Based loosely on libg++-1.2X malloc. (It retains some of the overall
2535          structure of old version,  but most details differ.)
2536
2537 */