common/dlmalloc.c

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