1/* $NetBSD: gmalloc.c,v 1.1.1.1 2016/01/13 21:42:18 christos Exp $ */ 2 3/* DO NOT EDIT THIS FILE -- it is automagically generated. -*- C -*- */ 4 5#define _MALLOC_INTERNAL 6 7/* The malloc headers and source files from the C library follow here. */ 8 9/* Declarations for `malloc' and friends. 10 Copyright 1990, 1991, 1992, 1993, 1995 Free Software Foundation, Inc. 11 Written May 1989 by Mike Haertel. 12 13This library is free software; you can redistribute it and/or 14modify it under the terms of the GNU Library General Public License as 15published by the Free Software Foundation; either version 2 of the 16License, or (at your option) any later version. 17 18This library is distributed in the hope that it will be useful, 19but WITHOUT ANY WARRANTY; without even the implied warranty of 20MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 21Library General Public License for more details. 22 23You should have received a copy of the GNU Library General Public 24License along with this library; see the file COPYING.LIB. If 25not, write to the Free Software Foundation, Inc., 675 Mass Ave, 26Cambridge, MA 02139, USA. 27 28 The author may be reached (Email) at the address mike@ai.mit.edu, 29 or (US mail) as Mike Haertel c/o Free Software Foundation. */ 30 31#ifndef _MALLOC_H 32 33#define _MALLOC_H 1 34 35#ifdef _MALLOC_INTERNAL 36 37#ifdef HAVE_CONFIG_H 38#include <config.h> 39#endif 40 41#if defined(_LIBC) || defined(STDC_HEADERS) || defined(USG) 42#include <string.h> 43#else 44#ifndef memset 45#define memset(s, zero, n) bzero ((s), (n)) 46#endif 47#ifndef memcpy 48#define memcpy(d, s, n) bcopy ((s), (d), (n)) 49#endif 50#endif 51 52#if defined (__GNU_LIBRARY__) || (defined (__STDC__) && __STDC__) 53#include <limits.h> 54#else 55#ifndef CHAR_BIT 56#define CHAR_BIT 8 57#endif 58#endif 59 60#ifdef HAVE_UNISTD_H 61#include <unistd.h> 62#endif 63 64#endif /* _MALLOC_INTERNAL. */ 65 66 67#ifdef __cplusplus 68extern "C" 69{ 70#endif 71 72#if defined (__cplusplus) || (defined (__STDC__) && __STDC__) 73#undef __P 74#define __P(args) args 75#undef __ptr_t 76#define __ptr_t void * 77#else /* Not C++ or ANSI C. */ 78#undef __P 79#define __P(args) () 80#undef const 81#define const 82#undef __ptr_t 83#define __ptr_t char * 84#endif /* C++ or ANSI C. */ 85 86#if defined (__STDC__) && __STDC__ 87#include <stddef.h> 88#define __malloc_size_t size_t 89#define __malloc_ptrdiff_t ptrdiff_t 90#else 91#define __malloc_size_t unsigned int 92#define __malloc_ptrdiff_t int 93#endif 94 95#ifndef NULL 96#define NULL 0 97#endif 98 99 100/* Allocate SIZE bytes of memory. */ 101extern __ptr_t malloc __P ((__malloc_size_t __size)); 102/* Re-allocate the previously allocated block 103 in __ptr_t, making the new block SIZE bytes long. */ 104extern __ptr_t realloc __P ((__ptr_t __ptr, __malloc_size_t __size)); 105/* Allocate NMEMB elements of SIZE bytes each, all initialized to 0. */ 106extern __ptr_t calloc __P ((__malloc_size_t __nmemb, __malloc_size_t __size)); 107/* Free a block allocated by `malloc', `realloc' or `calloc'. */ 108extern void free __P ((__ptr_t __ptr)); 109 110/* Allocate SIZE bytes allocated to ALIGNMENT bytes. */ 111extern __ptr_t memalign __P ((__malloc_size_t __alignment, 112 __malloc_size_t __size)); 113 114/* Allocate SIZE bytes on a page boundary. */ 115extern __ptr_t valloc __P ((__malloc_size_t __size)); 116 117 118#ifdef _MALLOC_INTERNAL 119 120/* The allocator divides the heap into blocks of fixed size; large 121 requests receive one or more whole blocks, and small requests 122 receive a fragment of a block. Fragment sizes are powers of two, 123 and all fragments of a block are the same size. When all the 124 fragments in a block have been freed, the block itself is freed. */ 125#define INT_BIT (CHAR_BIT * sizeof(int)) 126#define BLOCKLOG (INT_BIT > 16 ? 12 : 9) 127#define BLOCKSIZE (1 << BLOCKLOG) 128#define BLOCKIFY(SIZE) (((SIZE) + BLOCKSIZE - 1) / BLOCKSIZE) 129 130/* Determine the amount of memory spanned by the initial heap table 131 (not an absolute limit). */ 132#define HEAP (INT_BIT > 16 ? 4194304 : 65536) 133 134/* Number of contiguous free blocks allowed to build up at the end of 135 memory before they will be returned to the system. */ 136#define FINAL_FREE_BLOCKS 8 137 138/* Data structure giving per-block information. */ 139typedef union 140 { 141 /* Heap information for a busy block. */ 142 struct 143 { 144 /* Zero for a large (multiblock) object, or positive giving the 145 logarithm to the base two of the fragment size. */ 146 int type; 147 union 148 { 149 struct 150 { 151 __malloc_size_t nfree; /* Free frags in a fragmented block. */ 152 __malloc_size_t first; /* First free fragment of the block. */ 153 } frag; 154 /* For a large object, in its first block, this has the number 155 of blocks in the object. In the other blocks, this has a 156 negative number which says how far back the first block is. */ 157 __malloc_ptrdiff_t size; 158 } info; 159 } busy; 160 /* Heap information for a free block 161 (that may be the first of a free cluster). */ 162 struct 163 { 164 __malloc_size_t size; /* Size (in blocks) of a free cluster. */ 165 __malloc_size_t next; /* Index of next free cluster. */ 166 __malloc_size_t prev; /* Index of previous free cluster. */ 167 } free; 168 } malloc_info; 169 170/* Pointer to first block of the heap. */ 171extern char *_heapbase; 172 173/* Table indexed by block number giving per-block information. */ 174extern malloc_info *_heapinfo; 175 176/* Address to block number and vice versa. */ 177#define BLOCK(A) (((char *) (A) - _heapbase) / BLOCKSIZE + 1) 178#define ADDRESS(B) ((__ptr_t) (((B) - 1) * BLOCKSIZE + _heapbase)) 179 180/* Current search index for the heap table. */ 181extern __malloc_size_t _heapindex; 182 183/* Limit of valid info table indices. */ 184extern __malloc_size_t _heaplimit; 185 186/* Doubly linked lists of free fragments. */ 187struct list 188 { 189 struct list *next; 190 struct list *prev; 191 }; 192 193/* Free list headers for each fragment size. */ 194extern struct list _fraghead[]; 195 196/* List of blocks allocated with `memalign' (or `valloc'). */ 197struct alignlist 198 { 199 struct alignlist *next; 200 __ptr_t aligned; /* The address that memaligned returned. */ 201 __ptr_t exact; /* The address that malloc returned. */ 202 }; 203extern struct alignlist *_aligned_blocks; 204 205/* Instrumentation. */ 206extern __malloc_size_t _chunks_used; 207extern __malloc_size_t _bytes_used; 208extern __malloc_size_t _chunks_free; 209extern __malloc_size_t _bytes_free; 210 211/* Internal version of `free' used in `morecore' (malloc.c). */ 212extern void _free_internal __P ((__ptr_t __ptr)); 213 214#endif /* _MALLOC_INTERNAL. */ 215 216/* Given an address in the middle of a malloc'd object, 217 return the address of the beginning of the object. */ 218extern __ptr_t malloc_find_object_address __P ((__ptr_t __ptr)); 219 220/* Underlying allocation function; successive calls should 221 return contiguous pieces of memory. */ 222extern __ptr_t (*__morecore) __P ((__malloc_ptrdiff_t __size)); 223 224/* Default value of `__morecore'. */ 225extern __ptr_t __default_morecore __P ((__malloc_ptrdiff_t __size)); 226 227/* If not NULL, this function is called after each time 228 `__morecore' is called to increase the data size. */ 229extern void (*__after_morecore_hook) __P ((void)); 230 231/* Nonzero if `malloc' has been called and done its initialization. */ 232extern int __malloc_initialized; 233 234/* Hooks for debugging versions. */ 235extern void (*__malloc_initialize_hook) __P ((void)); 236extern void (*__free_hook) __P ((__ptr_t __ptr)); 237extern __ptr_t (*__malloc_hook) __P ((__malloc_size_t __size)); 238extern __ptr_t (*__realloc_hook) __P ((__ptr_t __ptr, __malloc_size_t __size)); 239extern __ptr_t (*__memalign_hook) __P ((__malloc_size_t __size, 240 __malloc_size_t __alignment)); 241 242/* Return values for `mprobe': these are the kinds of inconsistencies that 243 `mcheck' enables detection of. */ 244enum mcheck_status 245 { 246 MCHECK_DISABLED = -1, /* Consistency checking is not turned on. */ 247 MCHECK_OK, /* Block is fine. */ 248 MCHECK_FREE, /* Block freed twice. */ 249 MCHECK_HEAD, /* Memory before the block was clobbered. */ 250 MCHECK_TAIL /* Memory after the block was clobbered. */ 251 }; 252 253/* Activate a standard collection of debugging hooks. This must be called 254 before `malloc' is ever called. ABORTFUNC is called with an error code 255 (see enum above) when an inconsistency is detected. If ABORTFUNC is 256 null, the standard function prints on stderr and then calls `abort'. */ 257extern int mcheck __P ((void (*__abortfunc) __P ((enum mcheck_status)))); 258 259/* Check for aberrations in a particular malloc'd block. You must have 260 called `mcheck' already. These are the same checks that `mcheck' does 261 when you free or reallocate a block. */ 262extern enum mcheck_status mprobe __P ((__ptr_t __ptr)); 263 264/* Activate a standard collection of tracing hooks. */ 265extern void mtrace __P ((void)); 266extern void muntrace __P ((void)); 267 268/* Statistics available to the user. */ 269struct mstats 270 { 271 __malloc_size_t bytes_total; /* Total size of the heap. */ 272 __malloc_size_t chunks_used; /* Chunks allocated by the user. */ 273 __malloc_size_t bytes_used; /* Byte total of user-allocated chunks. */ 274 __malloc_size_t chunks_free; /* Chunks in the free list. */ 275 __malloc_size_t bytes_free; /* Byte total of chunks in the free list. */ 276 }; 277 278/* Pick up the current statistics. */ 279extern struct mstats mstats __P ((void)); 280 281/* Call WARNFUN with a warning message when memory usage is high. */ 282extern void memory_warnings __P ((__ptr_t __start, 283 void (*__warnfun) __P ((const char *)))); 284 285 286/* Relocating allocator. */ 287 288/* Allocate SIZE bytes, and store the address in *HANDLEPTR. */ 289extern __ptr_t r_alloc __P ((__ptr_t *__handleptr, __malloc_size_t __size)); 290 291/* Free the storage allocated in HANDLEPTR. */ 292extern void r_alloc_free __P ((__ptr_t *__handleptr)); 293 294/* Adjust the block at HANDLEPTR to be SIZE bytes long. */ 295extern __ptr_t r_re_alloc __P ((__ptr_t *__handleptr, __malloc_size_t __size)); 296 297 298#ifdef __cplusplus 299} 300#endif 301 302#endif /* malloc.h */ 303/* Allocate memory on a page boundary. 304 Copyright (C) 1991, 1992, 1993, 1994 Free Software Foundation, Inc. 305 306This library is free software; you can redistribute it and/or 307modify it under the terms of the GNU Library General Public License as 308published by the Free Software Foundation; either version 2 of the 309License, or (at your option) any later version. 310 311This library is distributed in the hope that it will be useful, 312but WITHOUT ANY WARRANTY; without even the implied warranty of 313MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 314Library General Public License for more details. 315 316You should have received a copy of the GNU Library General Public 317License along with this library; see the file COPYING.LIB. If 318not, write to the Free Software Foundation, Inc., 675 Mass Ave, 319Cambridge, MA 02139, USA. 320 321 The author may be reached (Email) at the address mike@ai.mit.edu, 322 or (US mail) as Mike Haertel c/o Free Software Foundation. */ 323 324#if defined (__GNU_LIBRARY__) || defined (_LIBC) 325#include <stddef.h> 326#include <sys/cdefs.h> 327extern size_t __getpagesize __P ((void)); 328#else 329#include "getpagesize.h" 330#define __getpagesize() getpagesize() 331#endif 332 333#ifndef _MALLOC_INTERNAL 334#define _MALLOC_INTERNAL 335#include <malloc.h> 336#endif 337 338static __malloc_size_t pagesize; 339 340__ptr_t 341valloc (size) 342 __malloc_size_t size; 343{ 344 if (pagesize == 0) 345 pagesize = __getpagesize (); 346 347 return memalign (pagesize, size); 348} 349/* Memory allocator `malloc'. 350 Copyright 1990, 1991, 1992, 1993, 1994, 1995 Free Software Foundation, Inc. 351 Written May 1989 by Mike Haertel. 352 353This library is free software; you can redistribute it and/or 354modify it under the terms of the GNU Library General Public License as 355published by the Free Software Foundation; either version 2 of the 356License, or (at your option) any later version. 357 358This library is distributed in the hope that it will be useful, 359but WITHOUT ANY WARRANTY; without even the implied warranty of 360MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 361Library General Public License for more details. 362 363You should have received a copy of the GNU Library General Public 364License along with this library; see the file COPYING.LIB. If 365not, write to the Free Software Foundation, Inc., 675 Mass Ave, 366Cambridge, MA 02139, USA. 367 368 The author may be reached (Email) at the address mike@ai.mit.edu, 369 or (US mail) as Mike Haertel c/o Free Software Foundation. */ 370 371#ifndef _MALLOC_INTERNAL 372#define _MALLOC_INTERNAL 373#include <malloc.h> 374#endif 375 376/* How to really get more memory. */ 377__ptr_t (*__morecore) __P ((ptrdiff_t __size)) = __default_morecore; 378 379/* Debugging hook for `malloc'. */ 380__ptr_t (*__malloc_hook) __P ((__malloc_size_t __size)); 381 382/* Pointer to the base of the first block. */ 383char *_heapbase; 384 385/* Block information table. Allocated with align/__free (not malloc/free). */ 386malloc_info *_heapinfo; 387 388/* Number of info entries. */ 389static __malloc_size_t heapsize; 390 391/* Search index in the info table. */ 392__malloc_size_t _heapindex; 393 394/* Limit of valid info table indices. */ 395__malloc_size_t _heaplimit; 396 397/* Free lists for each fragment size. */ 398struct list _fraghead[BLOCKLOG]; 399 400/* Instrumentation. */ 401__malloc_size_t _chunks_used; 402__malloc_size_t _bytes_used; 403__malloc_size_t _chunks_free; 404__malloc_size_t _bytes_free; 405 406/* Are you experienced? */ 407int __malloc_initialized; 408 409void (*__malloc_initialize_hook) __P ((void)); 410void (*__after_morecore_hook) __P ((void)); 411 412/* Aligned allocation. */ 413static __ptr_t align __P ((__malloc_size_t)); 414static __ptr_t 415align (size) 416 __malloc_size_t size; 417{ 418 __ptr_t result; 419 unsigned long int adj; 420 421 result = (*__morecore) (size); 422 adj = (unsigned long int) ((unsigned long int) ((char *) result - 423 (char *) NULL)) % BLOCKSIZE; 424 if (adj != 0) 425 { 426 adj = BLOCKSIZE - adj; 427 (void) (*__morecore) (adj); 428 result = (char *) result + adj; 429 } 430 431 if (__after_morecore_hook) 432 (*__after_morecore_hook) (); 433 434 return result; 435} 436 437/* Set everything up and remember that we have. */ 438static int initialize __P ((void)); 439static int 440initialize () 441{ 442 if (__malloc_initialize_hook) 443 (*__malloc_initialize_hook) (); 444 445 heapsize = HEAP / BLOCKSIZE; 446 _heapinfo = (malloc_info *) align (heapsize * sizeof (malloc_info)); 447 if (_heapinfo == NULL) 448 return 0; 449 memset (_heapinfo, 0, heapsize * sizeof (malloc_info)); 450 _heapinfo[0].free.size = 0; 451 _heapinfo[0].free.next = _heapinfo[0].free.prev = 0; 452 _heapindex = 0; 453 _heapbase = (char *) _heapinfo; 454 455 /* Account for the _heapinfo block itself in the statistics. */ 456 _bytes_used = heapsize * sizeof (malloc_info); 457 _chunks_used = 1; 458 459 __malloc_initialized = 1; 460 return 1; 461} 462 463/* Get neatly aligned memory, initializing or 464 growing the heap info table as necessary. */ 465static __ptr_t morecore __P ((__malloc_size_t)); 466static __ptr_t 467morecore (size) 468 __malloc_size_t size; 469{ 470 __ptr_t result; 471 malloc_info *newinfo, *oldinfo; 472 __malloc_size_t newsize; 473 474 result = align (size); 475 if (result == NULL) 476 return NULL; 477 478 /* Check if we need to grow the info table. */ 479 if ((__malloc_size_t) BLOCK ((char *) result + size) > heapsize) 480 { 481 newsize = heapsize; 482 while ((__malloc_size_t) BLOCK ((char *) result + size) > newsize) 483 newsize *= 2; 484 newinfo = (malloc_info *) align (newsize * sizeof (malloc_info)); 485 if (newinfo == NULL) 486 { 487 (*__morecore) (-size); 488 return NULL; 489 } 490 memcpy (newinfo, _heapinfo, heapsize * sizeof (malloc_info)); 491 memset (&newinfo[heapsize], 0, 492 (newsize - heapsize) * sizeof (malloc_info)); 493 oldinfo = _heapinfo; 494 newinfo[BLOCK (oldinfo)].busy.type = 0; 495 newinfo[BLOCK (oldinfo)].busy.info.size 496 = BLOCKIFY (heapsize * sizeof (malloc_info)); 497 _heapinfo = newinfo; 498 /* Account for the _heapinfo block itself in the statistics. */ 499 _bytes_used += newsize * sizeof (malloc_info); 500 ++_chunks_used; 501 _free_internal (oldinfo); 502 heapsize = newsize; 503 } 504 505 _heaplimit = BLOCK ((char *) result + size); 506 return result; 507} 508 509/* Allocate memory from the heap. */ 510__ptr_t 511malloc (size) 512 __malloc_size_t size; 513{ 514 __ptr_t result; 515 __malloc_size_t block, blocks, lastblocks, start; 516 register __malloc_size_t i; 517 struct list *next; 518 519 /* ANSI C allows `malloc (0)' to either return NULL, or to return a 520 valid address you can realloc and free (though not dereference). 521 522 It turns out that some extant code (sunrpc, at least Ultrix's version) 523 expects `malloc (0)' to return non-NULL and breaks otherwise. 524 Be compatible. */ 525 526#if 0 527 if (size == 0) 528 return NULL; 529#endif 530 531 if (__malloc_hook != NULL) 532 return (*__malloc_hook) (size); 533 534 if (!__malloc_initialized) 535 if (!initialize ()) 536 return NULL; 537 538 if (size < sizeof (struct list)) 539 size = sizeof (struct list); 540 541#ifdef SUNOS_LOCALTIME_BUG 542 if (size < 16) 543 size = 16; 544#endif 545 546 /* Determine the allocation policy based on the request size. */ 547 if (size <= BLOCKSIZE / 2) 548 { 549 /* Small allocation to receive a fragment of a block. 550 Determine the logarithm to base two of the fragment size. */ 551 register __malloc_size_t log = 1; 552 --size; 553 while ((size /= 2) != 0) 554 ++log; 555 556 /* Look in the fragment lists for a 557 free fragment of the desired size. */ 558 next = _fraghead[log].next; 559 if (next != NULL) 560 { 561 /* There are free fragments of this size. 562 Pop a fragment out of the fragment list and return it. 563 Update the block's nfree and first counters. */ 564 result = (__ptr_t) next; 565 next->prev->next = next->next; 566 if (next->next != NULL) 567 next->next->prev = next->prev; 568 block = BLOCK (result); 569 if (--_heapinfo[block].busy.info.frag.nfree != 0) 570 _heapinfo[block].busy.info.frag.first = (unsigned long int) 571 ((unsigned long int) ((char *) next->next - (char *) NULL) 572 % BLOCKSIZE) >> log; 573 574 /* Update the statistics. */ 575 ++_chunks_used; 576 _bytes_used += 1 << log; 577 --_chunks_free; 578 _bytes_free -= 1 << log; 579 } 580 else 581 { 582 /* No free fragments of the desired size, so get a new block 583 and break it into fragments, returning the first. */ 584 result = malloc (BLOCKSIZE); 585 if (result == NULL) 586 return NULL; 587 588 /* Link all fragments but the first into the free list. */ 589 for (i = 1; i < (__malloc_size_t) (BLOCKSIZE >> log); ++i) 590 { 591 next = (struct list *) ((char *) result + (i << log)); 592 next->next = _fraghead[log].next; 593 next->prev = &_fraghead[log]; 594 next->prev->next = next; 595 if (next->next != NULL) 596 next->next->prev = next; 597 } 598 599 /* Initialize the nfree and first counters for this block. */ 600 block = BLOCK (result); 601 _heapinfo[block].busy.type = log; 602 _heapinfo[block].busy.info.frag.nfree = i - 1; 603 _heapinfo[block].busy.info.frag.first = i - 1; 604 605 _chunks_free += (BLOCKSIZE >> log) - 1; 606 _bytes_free += BLOCKSIZE - (1 << log); 607 _bytes_used -= BLOCKSIZE - (1 << log); 608 } 609 } 610 else 611 { 612 /* Large allocation to receive one or more blocks. 613 Search the free list in a circle starting at the last place visited. 614 If we loop completely around without finding a large enough 615 space we will have to get more memory from the system. */ 616 blocks = BLOCKIFY (size); 617 start = block = _heapindex; 618 while (_heapinfo[block].free.size < blocks) 619 { 620 block = _heapinfo[block].free.next; 621 if (block == start) 622 { 623 /* Need to get more from the system. Check to see if 624 the new core will be contiguous with the final free 625 block; if so we don't need to get as much. */ 626 block = _heapinfo[0].free.prev; 627 lastblocks = _heapinfo[block].free.size; 628 if (_heaplimit != 0 && block + lastblocks == _heaplimit && 629 (*__morecore) (0) == ADDRESS (block + lastblocks) && 630 (morecore ((blocks - lastblocks) * BLOCKSIZE)) != NULL) 631 { 632 /* Which block we are extending (the `final free 633 block' referred to above) might have changed, if 634 it got combined with a freed info table. */ 635 block = _heapinfo[0].free.prev; 636 _heapinfo[block].free.size += (blocks - lastblocks); 637 _bytes_free += (blocks - lastblocks) * BLOCKSIZE; 638 continue; 639 } 640 result = morecore (blocks * BLOCKSIZE); 641 if (result == NULL) 642 return NULL; 643 block = BLOCK (result); 644 _heapinfo[block].busy.type = 0; 645 _heapinfo[block].busy.info.size = blocks; 646 ++_chunks_used; 647 _bytes_used += blocks * BLOCKSIZE; 648 return result; 649 } 650 } 651 652 /* At this point we have found a suitable free list entry. 653 Figure out how to remove what we need from the list. */ 654 result = ADDRESS (block); 655 if (_heapinfo[block].free.size > blocks) 656 { 657 /* The block we found has a bit left over, 658 so relink the tail end back into the free list. */ 659 _heapinfo[block + blocks].free.size 660 = _heapinfo[block].free.size - blocks; 661 _heapinfo[block + blocks].free.next 662 = _heapinfo[block].free.next; 663 _heapinfo[block + blocks].free.prev 664 = _heapinfo[block].free.prev; 665 _heapinfo[_heapinfo[block].free.prev].free.next 666 = _heapinfo[_heapinfo[block].free.next].free.prev 667 = _heapindex = block + blocks; 668 } 669 else 670 { 671 /* The block exactly matches our requirements, 672 so just remove it from the list. */ 673 _heapinfo[_heapinfo[block].free.next].free.prev 674 = _heapinfo[block].free.prev; 675 _heapinfo[_heapinfo[block].free.prev].free.next 676 = _heapindex = _heapinfo[block].free.next; 677 --_chunks_free; 678 } 679 680 _heapinfo[block].busy.type = 0; 681 _heapinfo[block].busy.info.size = blocks; 682 ++_chunks_used; 683 _bytes_used += blocks * BLOCKSIZE; 684 _bytes_free -= blocks * BLOCKSIZE; 685 686 /* Mark all the blocks of the object just allocated except for the 687 first with a negative number so you can find the first block by 688 adding that adjustment. */ 689 while (--blocks > 0) 690 _heapinfo[block + blocks].busy.info.size = -blocks; 691 } 692 693 return result; 694} 695 696#ifndef _LIBC 697 698/* On some ANSI C systems, some libc functions call _malloc, _free 699 and _realloc. Make them use the GNU functions. */ 700 701__ptr_t 702_malloc (size) 703 __malloc_size_t size; 704{ 705 return malloc (size); 706} 707 708void 709_free (ptr) 710 __ptr_t ptr; 711{ 712 free (ptr); 713} 714 715__ptr_t 716_realloc (ptr, size) 717 __ptr_t ptr; 718 __malloc_size_t size; 719{ 720 return realloc (ptr, size); 721} 722 723#endif 724/* Free a block of memory allocated by `malloc'. 725 Copyright 1990, 1991, 1992, 1994 Free Software Foundation, Inc. 726 Written May 1989 by Mike Haertel. 727 728This library is free software; you can redistribute it and/or 729modify it under the terms of the GNU Library General Public License as 730published by the Free Software Foundation; either version 2 of the 731License, or (at your option) any later version. 732 733This library is distributed in the hope that it will be useful, 734but WITHOUT ANY WARRANTY; without even the implied warranty of 735MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 736Library General Public License for more details. 737 738You should have received a copy of the GNU Library General Public 739License along with this library; see the file COPYING.LIB. If 740not, write to the Free Software Foundation, Inc., 675 Mass Ave, 741Cambridge, MA 02139, USA. 742 743 The author may be reached (Email) at the address mike@ai.mit.edu, 744 or (US mail) as Mike Haertel c/o Free Software Foundation. */ 745 746#ifndef _MALLOC_INTERNAL 747#define _MALLOC_INTERNAL 748#include <malloc.h> 749#endif 750 751/* Debugging hook for free. */ 752void (*__free_hook) __P ((__ptr_t __ptr)); 753 754/* List of blocks allocated by memalign. */ 755struct alignlist *_aligned_blocks = NULL; 756 757/* Return memory to the heap. 758 Like `free' but don't call a __free_hook if there is one. */ 759void 760_free_internal (ptr) 761 __ptr_t ptr; 762{ 763 int type; 764 __malloc_size_t block, blocks; 765 register __malloc_size_t i; 766 struct list *prev, *next; 767 768 block = BLOCK (ptr); 769 770 type = _heapinfo[block].busy.type; 771 switch (type) 772 { 773 case 0: 774 /* Get as many statistics as early as we can. */ 775 --_chunks_used; 776 _bytes_used -= _heapinfo[block].busy.info.size * BLOCKSIZE; 777 _bytes_free += _heapinfo[block].busy.info.size * BLOCKSIZE; 778 779 /* Find the free cluster previous to this one in the free list. 780 Start searching at the last block referenced; this may benefit 781 programs with locality of allocation. */ 782 i = _heapindex; 783 if (i > block) 784 while (i > block) 785 i = _heapinfo[i].free.prev; 786 else 787 { 788 do 789 i = _heapinfo[i].free.next; 790 while (i > 0 && i < block); 791 i = _heapinfo[i].free.prev; 792 } 793 794 /* Determine how to link this block into the free list. */ 795 if (block == i + _heapinfo[i].free.size) 796 { 797 /* Coalesce this block with its predecessor. */ 798 _heapinfo[i].free.size += _heapinfo[block].busy.info.size; 799 block = i; 800 } 801 else 802 { 803 /* Really link this block back into the free list. */ 804 _heapinfo[block].free.size = _heapinfo[block].busy.info.size; 805 _heapinfo[block].free.next = _heapinfo[i].free.next; 806 _heapinfo[block].free.prev = i; 807 _heapinfo[i].free.next = block; 808 _heapinfo[_heapinfo[block].free.next].free.prev = block; 809 ++_chunks_free; 810 } 811 812 /* Now that the block is linked in, see if we can coalesce it 813 with its successor (by deleting its successor from the list 814 and adding in its size). */ 815 if (block + _heapinfo[block].free.size == _heapinfo[block].free.next) 816 { 817 _heapinfo[block].free.size 818 += _heapinfo[_heapinfo[block].free.next].free.size; 819 _heapinfo[block].free.next 820 = _heapinfo[_heapinfo[block].free.next].free.next; 821 _heapinfo[_heapinfo[block].free.next].free.prev = block; 822 --_chunks_free; 823 } 824 825 /* Now see if we can return stuff to the system. */ 826 blocks = _heapinfo[block].free.size; 827 if (blocks >= FINAL_FREE_BLOCKS && block + blocks == _heaplimit 828 && (*__morecore) (0) == ADDRESS (block + blocks)) 829 { 830 register __malloc_size_t bytes = blocks * BLOCKSIZE; 831 _heaplimit -= blocks; 832 (*__morecore) (-bytes); 833 _heapinfo[_heapinfo[block].free.prev].free.next 834 = _heapinfo[block].free.next; 835 _heapinfo[_heapinfo[block].free.next].free.prev 836 = _heapinfo[block].free.prev; 837 block = _heapinfo[block].free.prev; 838 --_chunks_free; 839 _bytes_free -= bytes; 840 } 841 842 /* Set the next search to begin at this block. */ 843 _heapindex = block; 844 break; 845 846 default: 847 /* Do some of the statistics. */ 848 --_chunks_used; 849 _bytes_used -= 1 << type; 850 ++_chunks_free; 851 _bytes_free += 1 << type; 852 853 /* Get the address of the first free fragment in this block. */ 854 prev = (struct list *) ((char *) ADDRESS (block) + 855 (_heapinfo[block].busy.info.frag.first << type)); 856 857 if (_heapinfo[block].busy.info.frag.nfree == (BLOCKSIZE >> type) - 1) 858 { 859 /* If all fragments of this block are free, remove them 860 from the fragment list and free the whole block. */ 861 next = prev; 862 for (i = 1; i < (__malloc_size_t) (BLOCKSIZE >> type); ++i) 863 next = next->next; 864 prev->prev->next = next; 865 if (next != NULL) 866 next->prev = prev->prev; 867 _heapinfo[block].busy.type = 0; 868 _heapinfo[block].busy.info.size = 1; 869 870 /* Keep the statistics accurate. */ 871 ++_chunks_used; 872 _bytes_used += BLOCKSIZE; 873 _chunks_free -= BLOCKSIZE >> type; 874 _bytes_free -= BLOCKSIZE; 875 876 free (ADDRESS (block)); 877 } 878 else if (_heapinfo[block].busy.info.frag.nfree != 0) 879 { 880 /* If some fragments of this block are free, link this 881 fragment into the fragment list after the first free 882 fragment of this block. */ 883 next = (struct list *) ptr; 884 next->next = prev->next; 885 next->prev = prev; 886 prev->next = next; 887 if (next->next != NULL) 888 next->next->prev = next; 889 ++_heapinfo[block].busy.info.frag.nfree; 890 } 891 else 892 { 893 /* No fragments of this block are free, so link this 894 fragment into the fragment list and announce that 895 it is the first free fragment of this block. */ 896 prev = (struct list *) ptr; 897 _heapinfo[block].busy.info.frag.nfree = 1; 898 _heapinfo[block].busy.info.frag.first = (unsigned long int) 899 ((unsigned long int) ((char *) ptr - (char *) NULL) 900 % BLOCKSIZE >> type); 901 prev->next = _fraghead[type].next; 902 prev->prev = &_fraghead[type]; 903 prev->prev->next = prev; 904 if (prev->next != NULL) 905 prev->next->prev = prev; 906 } 907 break; 908 } 909} 910 911/* Return memory to the heap. */ 912void 913free (ptr) 914 __ptr_t ptr; 915{ 916 register struct alignlist *l; 917 918 if (ptr == NULL) 919 return; 920 921 for (l = _aligned_blocks; l != NULL; l = l->next) 922 if (l->aligned == ptr) 923 { 924 l->aligned = NULL; /* Mark the slot in the list as free. */ 925 ptr = l->exact; 926 break; 927 } 928 929 if (__free_hook != NULL) 930 (*__free_hook) (ptr); 931 else 932 _free_internal (ptr); 933} 934/* Copyright (C) 1991, 1993, 1994 Free Software Foundation, Inc. 935This file is part of the GNU C Library. 936 937The GNU C Library is free software; you can redistribute it and/or 938modify it under the terms of the GNU Library General Public License as 939published by the Free Software Foundation; either version 2 of the 940License, or (at your option) any later version. 941 942The GNU C Library is distributed in the hope that it will be useful, 943but WITHOUT ANY WARRANTY; without even the implied warranty of 944MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 945Library General Public License for more details. 946 947You should have received a copy of the GNU Library General Public 948License along with the GNU C Library; see the file COPYING.LIB. If 949not, write to the Free Software Foundation, Inc., 675 Mass Ave, 950Cambridge, MA 02139, USA. */ 951 952#ifndef _MALLOC_INTERNAL 953#define _MALLOC_INTERNAL 954#include <malloc.h> 955#endif 956 957#ifdef _LIBC 958 959#include <ansidecl.h> 960#include <gnu-stabs.h> 961 962#undef cfree 963 964function_alias(cfree, free, void, (ptr), 965 DEFUN(cfree, (ptr), PTR ptr)) 966 967#else 968 969void 970cfree (ptr) 971 __ptr_t ptr; 972{ 973 free (ptr); 974} 975 976#endif 977/* Change the size of a block allocated by `malloc'. 978 Copyright 1990, 1991, 1992, 1993, 1994 Free Software Foundation, Inc. 979 Written May 1989 by Mike Haertel. 980 981This library is free software; you can redistribute it and/or 982modify it under the terms of the GNU Library General Public License as 983published by the Free Software Foundation; either version 2 of the 984License, or (at your option) any later version. 985 986This library is distributed in the hope that it will be useful, 987but WITHOUT ANY WARRANTY; without even the implied warranty of 988MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 989Library General Public License for more details. 990 991You should have received a copy of the GNU Library General Public 992License along with this library; see the file COPYING.LIB. If 993not, write to the Free Software Foundation, Inc., 675 Mass Ave, 994Cambridge, MA 02139, USA. 995 996 The author may be reached (Email) at the address mike@ai.mit.edu, 997 or (US mail) as Mike Haertel c/o Free Software Foundation. */ 998 999#ifndef _MALLOC_INTERNAL 1000#define _MALLOC_INTERNAL 1001#include <malloc.h> 1002#endif 1003 1004#if (defined (MEMMOVE_MISSING) || \ 1005 !defined(_LIBC) && !defined(STDC_HEADERS) && !defined(USG)) 1006 1007/* Snarfed directly from Emacs src/dispnew.c: 1008 XXX Should use system bcopy if it handles overlap. */ 1009#ifndef emacs 1010 1011/* Like bcopy except never gets confused by overlap. */ 1012 1013static void 1014safe_bcopy (from, to, size) 1015 char *from, *to; 1016 int size; 1017{ 1018 if (size <= 0 || from == to) 1019 return; 1020 1021 /* If the source and destination don't overlap, then bcopy can 1022 handle it. If they do overlap, but the destination is lower in 1023 memory than the source, we'll assume bcopy can handle that. */ 1024 if (to < from || from + size <= to) 1025 bcopy (from, to, size); 1026 1027 /* Otherwise, we'll copy from the end. */ 1028 else 1029 { 1030 register char *endf = from + size; 1031 register char *endt = to + size; 1032 1033 /* If TO - FROM is large, then we should break the copy into 1034 nonoverlapping chunks of TO - FROM bytes each. However, if 1035 TO - FROM is small, then the bcopy function call overhead 1036 makes this not worth it. The crossover point could be about 1037 anywhere. Since I don't think the obvious copy loop is too 1038 bad, I'm trying to err in its favor. */ 1039 if (to - from < 64) 1040 { 1041 do 1042 *--endt = *--endf; 1043 while (endf != from); 1044 } 1045 else 1046 { 1047 for (;;) 1048 { 1049 endt -= (to - from); 1050 endf -= (to - from); 1051 1052 if (endt < to) 1053 break; 1054 1055 bcopy (endf, endt, to - from); 1056 } 1057 1058 /* If SIZE wasn't a multiple of TO - FROM, there will be a 1059 little left over. The amount left over is 1060 (endt + (to - from)) - to, which is endt - from. */ 1061 bcopy (from, to, endt - from); 1062 } 1063 } 1064} 1065#endif /* Not emacs. */ 1066 1067#define memmove(to, from, size) safe_bcopy ((from), (to), (size)) 1068 1069#endif 1070 1071 1072#define min(A, B) ((A) < (B) ? (A) : (B)) 1073 1074/* Debugging hook for realloc. */ 1075__ptr_t (*__realloc_hook) __P ((__ptr_t __ptr, __malloc_size_t __size)); 1076 1077/* Resize the given region to the new size, returning a pointer 1078 to the (possibly moved) region. This is optimized for speed; 1079 some benchmarks seem to indicate that greater compactness is 1080 achieved by unconditionally allocating and copying to a 1081 new region. This module has incestuous knowledge of the 1082 internals of both free and malloc. */ 1083__ptr_t 1084realloc (ptr, size) 1085 __ptr_t ptr; 1086 __malloc_size_t size; 1087{ 1088 __ptr_t result; 1089 int type; 1090 __malloc_size_t block, blocks, oldlimit; 1091 1092 if (size == 0) 1093 { 1094 free (ptr); 1095 return malloc (0); 1096 } 1097 else if (ptr == NULL) 1098 return malloc (size); 1099 1100 if (__realloc_hook != NULL) 1101 return (*__realloc_hook) (ptr, size); 1102 1103 block = BLOCK (ptr); 1104 1105 type = _heapinfo[block].busy.type; 1106 switch (type) 1107 { 1108 case 0: 1109 /* Maybe reallocate a large block to a small fragment. */ 1110 if (size <= BLOCKSIZE / 2) 1111 { 1112 result = malloc (size); 1113 if (result != NULL) 1114 { 1115 memcpy (result, ptr, size); 1116 _free_internal (ptr); 1117 return result; 1118 } 1119 } 1120 1121 /* The new size is a large allocation as well; 1122 see if we can hold it in place. */ 1123 blocks = BLOCKIFY (size); 1124 if (blocks < _heapinfo[block].busy.info.size) 1125 { 1126 /* The new size is smaller; return 1127 excess memory to the free list. */ 1128 _heapinfo[block + blocks].busy.type = 0; 1129 _heapinfo[block + blocks].busy.info.size 1130 = _heapinfo[block].busy.info.size - blocks; 1131 _heapinfo[block].busy.info.size = blocks; 1132 /* We have just created a new chunk by splitting a chunk in two. 1133 Now we will free this chunk; increment the statistics counter 1134 so it doesn't become wrong when _free_internal decrements it. */ 1135 ++_chunks_used; 1136 _free_internal (ADDRESS (block + blocks)); 1137 result = ptr; 1138 } 1139 else if (blocks == _heapinfo[block].busy.info.size) 1140 /* No size change necessary. */ 1141 result = ptr; 1142 else 1143 { 1144 /* Won't fit, so allocate a new region that will. 1145 Free the old region first in case there is sufficient 1146 adjacent free space to grow without moving. */ 1147 blocks = _heapinfo[block].busy.info.size; 1148 /* Prevent free from actually returning memory to the system. */ 1149 oldlimit = _heaplimit; 1150 _heaplimit = 0; 1151 _free_internal (ptr); 1152 _heaplimit = oldlimit; 1153 result = malloc (size); 1154 if (result == NULL) 1155 { 1156 /* Now we're really in trouble. We have to unfree 1157 the thing we just freed. Unfortunately it might 1158 have been coalesced with its neighbors. */ 1159 if (_heapindex == block) 1160 (void) malloc (blocks * BLOCKSIZE); 1161 else 1162 { 1163 __ptr_t previous = malloc ((block - _heapindex) * BLOCKSIZE); 1164 (void) malloc (blocks * BLOCKSIZE); 1165 _free_internal (previous); 1166 } 1167 return NULL; 1168 } 1169 if (ptr != result) 1170 memmove (result, ptr, blocks * BLOCKSIZE); 1171 } 1172 break; 1173 1174 default: 1175 /* Old size is a fragment; type is logarithm 1176 to base two of the fragment size. */ 1177 if (size > (__malloc_size_t) (1 << (type - 1)) && 1178 size <= (__malloc_size_t) (1 << type)) 1179 /* The new size is the same kind of fragment. */ 1180 result = ptr; 1181 else 1182 { 1183 /* The new size is different; allocate a new space, 1184 and copy the lesser of the new size and the old. */ 1185 result = malloc (size); 1186 if (result == NULL) 1187 return NULL; 1188 memcpy (result, ptr, min (size, (__malloc_size_t) 1 << type)); 1189 free (ptr); 1190 } 1191 break; 1192 } 1193 1194 return result; 1195} 1196/* Copyright (C) 1991, 1992, 1994 Free Software Foundation, Inc. 1197 1198This library is free software; you can redistribute it and/or 1199modify it under the terms of the GNU Library General Public License as 1200published by the Free Software Foundation; either version 2 of the 1201License, or (at your option) any later version. 1202 1203This library is distributed in the hope that it will be useful, 1204but WITHOUT ANY WARRANTY; without even the implied warranty of 1205MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1206Library General Public License for more details. 1207 1208You should have received a copy of the GNU Library General Public 1209License along with this library; see the file COPYING.LIB. If 1210not, write to the Free Software Foundation, Inc., 675 Mass Ave, 1211Cambridge, MA 02139, USA. 1212 1213 The author may be reached (Email) at the address mike@ai.mit.edu, 1214 or (US mail) as Mike Haertel c/o Free Software Foundation. */ 1215 1216#ifndef _MALLOC_INTERNAL 1217#define _MALLOC_INTERNAL 1218#include <malloc.h> 1219#endif 1220 1221/* Allocate an array of NMEMB elements each SIZE bytes long. 1222 The entire array is initialized to zeros. */ 1223__ptr_t 1224calloc (nmemb, size) 1225 register __malloc_size_t nmemb; 1226 register __malloc_size_t size; 1227{ 1228 register __ptr_t result = malloc (nmemb * size); 1229 1230 if (result != NULL) 1231 (void) memset (result, 0, nmemb * size); 1232 1233 return result; 1234} 1235/* Copyright (C) 1991, 1992, 1993, 1994 Free Software Foundation, Inc. 1236This file is part of the GNU C Library. 1237 1238The GNU C Library is free software; you can redistribute it and/or modify 1239it under the terms of the GNU General Public License as published by 1240the Free Software Foundation; either version 2, or (at your option) 1241any later version. 1242 1243The GNU C Library is distributed in the hope that it will be useful, 1244but WITHOUT ANY WARRANTY; without even the implied warranty of 1245MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1246GNU General Public License for more details. 1247 1248You should have received a copy of the GNU General Public License 1249along with the GNU C Library; see the file COPYING. If not, write to 1250the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ 1251 1252#ifndef _MALLOC_INTERNAL 1253#define _MALLOC_INTERNAL 1254#include <malloc.h> 1255#endif 1256 1257#ifndef __GNU_LIBRARY__ 1258#define __sbrk sbrk 1259#endif 1260 1261#ifdef __GNU_LIBRARY__ 1262/* It is best not to declare this and cast its result on foreign operating 1263 systems with potentially hostile include files. */ 1264extern __ptr_t __sbrk __P ((int increment)); 1265#endif 1266 1267#ifndef NULL 1268#define NULL 0 1269#endif 1270 1271/* Allocate INCREMENT more bytes of data space, 1272 and return the start of data space, or NULL on errors. 1273 If INCREMENT is negative, shrink data space. */ 1274__ptr_t 1275__default_morecore (increment) 1276#ifdef __STDC__ 1277 ptrdiff_t increment; 1278#else 1279 int increment; 1280#endif 1281{ 1282 __ptr_t result = (__ptr_t) __sbrk ((int) increment); 1283 if (result == (__ptr_t) -1) 1284 return NULL; 1285 return result; 1286} 1287/* Copyright (C) 1991, 1992, 1993, 1994, 1995 Free Software Foundation, Inc. 1288 1289This library is free software; you can redistribute it and/or 1290modify it under the terms of the GNU Library General Public License as 1291published by the Free Software Foundation; either version 2 of the 1292License, or (at your option) any later version. 1293 1294This library is distributed in the hope that it will be useful, 1295but WITHOUT ANY WARRANTY; without even the implied warranty of 1296MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1297Library General Public License for more details. 1298 1299You should have received a copy of the GNU Library General Public 1300License along with this library; see the file COPYING.LIB. If 1301not, write to the Free Software Foundation, Inc., 675 Mass Ave, 1302Cambridge, MA 02139, USA. */ 1303 1304#ifndef _MALLOC_INTERNAL 1305#define _MALLOC_INTERNAL 1306#include <malloc.h> 1307#endif 1308 1309__ptr_t (*__memalign_hook) __P ((size_t __size, size_t __alignment)); 1310 1311__ptr_t 1312memalign (alignment, size) 1313 __malloc_size_t alignment; 1314 __malloc_size_t size; 1315{ 1316 __ptr_t result; 1317 unsigned long int adj; 1318 1319 if (__memalign_hook) 1320 return (*__memalign_hook) (alignment, size); 1321 1322 size = ((size + alignment - 1) / alignment) * alignment; 1323 1324 result = malloc (size); 1325 if (result == NULL) 1326 return NULL; 1327 adj = (unsigned long int) ((unsigned long int) ((char *) result - 1328 (char *) NULL)) % alignment; 1329 if (adj != 0) 1330 { 1331 struct alignlist *l; 1332 for (l = _aligned_blocks; l != NULL; l = l->next) 1333 if (l->aligned == NULL) 1334 /* This slot is free. Use it. */ 1335 break; 1336 if (l == NULL) 1337 { 1338 l = (struct alignlist *) malloc (sizeof (struct alignlist)); 1339 if (l == NULL) 1340 { 1341 free (result); 1342 return NULL; 1343 } 1344 l->next = _aligned_blocks; 1345 _aligned_blocks = l; 1346 } 1347 l->exact = result; 1348 result = l->aligned = (char *) result + alignment - adj; 1349 } 1350 1351 return result; 1352} 1353