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