gdb/gmalloc.c

   1
   2 /* gmalloc.c - THIS FILE IS AUTOMAGICALLY GENERATED SO DON'T EDIT IT. */
   3
   4 /* Single-file skeleton for GNU malloc.
   5    Copyright 1989 Free Software Foundation
   6                   Written May 1989 by Mike Haertel.
   7
   8    The author may be reached (Email) at the address mike@ai.mit.edu,
   9    or (US mail) as Mike Haertel c/o Free Software Foundation.
  10
  11 This program is free software; you can redistribute it and/or modify
  12 it under the terms of the GNU General Public License as published by
  13 the Free Software Foundation; either version 2 of the License, or
  14 (at your option) any later version.
  15
  16 This program is distributed in the hope that it will be useful,
  17 but WITHOUT ANY WARRANTY; without even the implied warranty of
  18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19 GNU General Public License for more details.
  20
  21 You should have received a copy of the GNU General Public License
  22 along with this program; if not, write to the Free Software
  23 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
  24
  25 #define __ONEFILE
  26
  27 /* DO NOT DELETE THIS LINE -- ansidecl.h INSERTED HERE. */
  28 /* Copyright (C) 1989 Free Software Foundation, Inc.
  29 This file is part of the GNU C Library.
  30
  31 This program is free software; you can redistribute it and/or modify
  32 it under the terms of the GNU General Public License as published by
  33 the Free Software Foundation; either version 2 of the License, or
  34 (at your option) any later version.
  35
  36 This program is distributed in the hope that it will be useful,
  37 but WITHOUT ANY WARRANTY; without even the implied warranty of
  38 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  39 GNU General Public License for more details.
  40
  41 You should have received a copy of the GNU General Public License
  42 along with this program; if not, write to the Free Software
  43 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
  44
  45 /* ANSI and traditional C compatibility macros
  46
  47    ANSI C is assumed if __STDC__ is #defined.
  48
  49         Macros
  50                 PTR             - Generic pointer type
  51                 LONG_DOUBLE     - `long double' type
  52                 CONST           - `const' keyword
  53                 VOLATILE        - `volatile' keyword
  54                 SIGNED          - `signed' keyword
  55                 PTRCONST        - Generic const pointer (void *const)
  56
  57         EXFUN(name, prototype)          - declare external function NAME
  58                                           with prototype PROTOTYPE
  59         DEFUN(name, arglist, args)      - define function NAME with
  60                                           args ARGLIST of types in ARGS
  61         DEFUN_VOID(name)                - define function NAME with no args
  62         AND                             - argument separator for ARGS
  63         NOARGS                          - null arglist
  64         DOTS                            - `...' in args
  65
  66     For example:
  67         extern int EXFUN(printf, (CONST char *format DOTS));
  68         int DEFUN(fprintf, (stream, format),
  69                   FILE *stream AND CONST char *format DOTS) { ... }
  70         void DEFUN_VOID(abort) { ... }
  71 */
  72
  73 #ifndef _ANSIDECL_H
  74
  75 #define _ANSIDECL_H     1
  76
  77
  78 /* Every source file includes this file,
  79    so they will all get the switch for lint.  */
  80 /* LINTLIBRARY */
  81
  82
  83 #ifdef  __STDC__
  84
  85 #define PTR             void *
  86 #define PTRCONST        void *CONST
  87 #define LONG_DOUBLE     long double
  88
  89 #define AND             ,
  90 #define NOARGS          void
  91 #define CONST           const
  92 #define VOLATILE        volatile
  93 #define SIGNED          signed
  94 #define DOTS            , ...
  95
  96 #define EXFUN(name, proto)              name proto
  97 #define DEFUN(name, arglist, args)      name(args)
  98 #define DEFUN_VOID(name)                name(NOARGS)
  99
 100 #else   /* Not ANSI C.  */
 101
 102 #define PTR             char *
 103 #define PTRCONST        PTR
 104 #define LONG_DOUBLE     double
 105
 106 #define AND             ;
 107 #define NOARGS
 108 #define CONST
 109 #define VOLATILE
 110 #define SIGNED
 111 #define DOTS
 112
 113 #define EXFUN(name, proto)              name()
 114 #define DEFUN(name, arglist, args)      name arglist args;
 115 #define DEFUN_VOID(name)                name()
 116
 117 #endif  /* ANSI C.  */
 118
 119
 120 #endif  /* ansidecl.h   */
 121
 122 #ifdef __STDC__
 123 #include <limits.h>
 124 #else
 125 /* DO NOT DELETE THIS LINE -- limits.h INSERTED HERE. */
 126 /* Number of bits in a `char'.  */
 127 #define CHAR_BIT 8
 128
 129 /* No multibyte characters supported yet.  */
 130 #define MB_LEN_MAX 1
 131
 132 /* Minimum and maximum values a `signed char' can hold.  */
 133 #define SCHAR_MIN -128
 134 #define SCHAR_MAX 127
 135
 136 /* Maximum value an `unsigned char' can hold.  (Minimum is 0).  */
 137 #define UCHAR_MAX 255U
 138
 139 /* Minimum and maximum values a `char' can hold.  */
 140 #ifdef __CHAR_UNSIGNED__
 141 #define CHAR_MIN 0
 142 #define CHAR_MAX 255U
 143 #else
 144 #define CHAR_MIN -128
 145 #define CHAR_MAX 127
 146 #endif
 147
 148 /* Minimum and maximum values a `signed short int' can hold.  */
 149 #define SHRT_MIN -32768
 150 #define SHRT_MAX 32767
 151
 152 /* Maximum value an `unsigned short int' can hold.  (Minimum is 0).  */
 153 #define USHRT_MAX 65535U
 154
 155 /* Minimum and maximum values a `signed int' can hold.  */
 156 #define INT_MIN -2147483648
 157 #define INT_MAX 2147483647
 158
 159 /* Maximum value an `unsigned int' can hold.  (Minimum is 0).  */
 160 #define UINT_MAX 4294967295U
 161
 162 /* Minimum and maximum values a `signed long int' can hold.
 163    (Same as `int').  */
 164 #define LONG_MIN (-LONG_MAX-1)
 165 #define LONG_MAX 2147483647
 166
 167 /* Maximum value an `unsigned long int' can hold.  (Minimum is 0).  */
 168 #define ULONG_MAX 4294967295U
 169 #endif
 170
 171 #ifdef __STDC__
 172 #include <stddef.h>
 173 #else
 174 /* DO NOT DELETE THIS LINE -- stddef.h INSERTED HERE. */
 175 #ifndef _STDDEF_H
 176 #define _STDDEF_H
 177
 178 /* Signed type of difference of two pointers.  */
 179
 180 typedef long ptrdiff_t;
 181
 182 /* Unsigned type of `sizeof' something.  */
 183
 184 #ifndef _SIZE_T /* in case <sys/types.h> has defined it. */
 185 #define _SIZE_T
 186 typedef unsigned long size_t;
 187 #endif /* _SIZE_T */
 188
 189 /* A null pointer constant.  */
 190
 191 #undef NULL             /* in case <stdio.h> has defined it. */
 192 #define NULL 0
 193
 194 /* Offset of member MEMBER in a struct of type TYPE.  */
 195
 196 #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
 197
 198 #endif /* _STDDEF_H */
 199 #endif
 200
 201 /* DO NOT DELETE THIS LINE -- stdlib.h INSERTED HERE. */
 202 /* Fake stdlib.h supplying the stuff needed by malloc. */
 203
 204 #ifndef __ONEFILE
 205 #include <stddef.h>
 206 #endif
 207
 208 extern void EXFUN(abort, (NOARGS));
 209 extern void EXFUN(free, (PTR));
 210 extern PTR EXFUN(malloc, (size_t));
 211 extern PTR EXFUN(realloc, (PTR, size_t));
 212
 213 /* DO NOT DELETE THIS LINE -- string.h INSERTED HERE. */
 214 /* Fake string.h supplying stuff used by malloc. */
 215 #ifndef __ONEFILE
 216 #include <stddef.h>
 217 #endif
 218
 219 extern PTR EXFUN(memcpy, (PTR, CONST PTR, size_t));
 220 extern PTR EXFUN(memset, (PTR, int, size_t));
 221 #define memmove memcpy
 222
 223 #define _MALLOC_INTERNAL
 224 /* DO NOT DELETE THIS LINE -- malloc.h INSERTED HERE. */
 225 /* Declarations for `malloc' and friends.
 226    Copyright 1990 Free Software Foundation
 227                   Written May 1989 by Mike Haertel.
 228
 229    The author may be reached (Email) at the address mike@ai.mit.edu,
 230    or (US mail) as Mike Haertel c/o Free Software Foundation.
 231
 232 This program is free software; you can redistribute it and/or modify
 233 it under the terms of the GNU General Public License as published by
 234 the Free Software Foundation; either version 2 of the License, or
 235 (at your option) any later version.
 236
 237 This program is distributed in the hope that it will be useful,
 238 but WITHOUT ANY WARRANTY; without even the implied warranty of
 239 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 240 GNU General Public License for more details.
 241
 242 You should have received a copy of the GNU General Public License
 243 along with this program; if not, write to the Free Software
 244 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
 245
 246 #ifndef _MALLOC_H
 247
 248 #define _MALLOC_H       1
 249
 250 #ifndef __ONEFILE
 251 #define __need_NULL
 252 #define __need_size_t
 253 #define __need_ptrdiff_t
 254 #include <stddef.h>
 255 #endif
 256
 257 #ifdef _MALLOC_INTERNAL
 258
 259 #ifndef __ONEFILE
 260 #include <limits.h>
 261 #endif
 262
 263 /* The allocator divides the heap into blocks of fixed size; large
 264    requests receive one or more whole blocks, and small requests
 265    receive a fragment of a block.  Fragment sizes are powers of two,
 266    and all fragments of a block are the same size.  When all the
 267    fragments in a block have been freed, the block itself is freed.  */
 268 #define INT_BIT         (CHAR_BIT * sizeof(int))
 269 #define BLOCKLOG        (INT_BIT > 16 ? 12 : 9)
 270 #define BLOCKSIZE       ((unsigned int) 1 << BLOCKLOG)
 271 #define BLOCKIFY(SIZE)  (((SIZE) + BLOCKSIZE - 1) / BLOCKSIZE)
 272
 273 /* The difference between two pointers is a signed int.  On machines where
 274    the data addresses have the high bit set, we need to ensure that the
 275    difference becomes an unsigned int when we are using the address as an
 276    integral value.  In addition, when using with the '%' operator, the
 277    sign of the result is machine dependent for negative values, so force
 278    it to be treated as an unsigned int. */
 279
 280 #define ADDR2UINT(addr) ((unsigned int) ((char *) (addr) - (char *) NULL))
 281 #define RESIDUAL(addr)  ((unsigned int) (ADDR2UINT (addr) % BLOCKSIZE))
 282
 283 /* Determine the amount of memory spanned by the initial heap table
 284    (not an absolute limit).  */
 285 #define HEAP            (INT_BIT > 16 ? 4194304 : 65536)
 286
 287 /* Number of contiguous free blocks allowed to build up at the end of
 288    memory before they will be returned to the system.  */
 289 #define FINAL_FREE_BLOCKS       8
 290
 291 /* Where to start searching the free list when looking for new memory.
 292    The two possible values are 0 and _heapindex.  Starting at 0 seems
 293    to reduce total memory usage, while starting at _heapindex seems to
 294    run faster.  */
 295 #define MALLOC_SEARCH_START     _heapindex
 296
 297 /* Data structure giving per-block information.  */
 298 typedef union
 299   {
 300     /* Heap information for a busy block.  */
 301     struct
 302       {
 303         /* Zero for a large block, or positive giving the
 304            logarithm to the base two of the fragment size.  */
 305         int type;
 306         union
 307           {
 308             struct
 309               {
 310                 size_t nfree;   /* Free fragments in a fragmented block.  */
 311                 size_t first;   /* First free fragment of the block.  */
 312               } frag;
 313             /* Size (in blocks) of a large cluster.  */
 314             size_t size;
 315           } info;
 316       } busy;
 317     /* Heap information for a free block (that may be the first of
 318        a free cluster).  */
 319     struct
 320       {
 321         size_t size;            /* Size (in blocks) of a free cluster.  */
 322         size_t next;            /* Index of next free cluster.  */
 323         size_t prev;            /* Index of previous free cluster.  */
 324       } free;
 325   } malloc_info;
 326
 327 /* Pointer to first block of the heap.  */
 328 extern char *_heapbase;
 329
 330 /* Table indexed by block number giving per-block information.  */
 331 extern malloc_info *_heapinfo;
 332
 333 /* Address to block number and vice versa.  */
 334 #define BLOCK(A) (((char *) (A) - _heapbase) / BLOCKSIZE + 1)
 335 #define ADDRESS(B) ((PTR) (((B) - 1) * BLOCKSIZE + _heapbase))
 336
 337 /* Current search index for the heap table.  */
 338 extern size_t _heapindex;
 339
 340 /* Limit of valid info table indices.  */
 341 extern size_t _heaplimit;
 342
 343 /* Doubly linked lists of free fragments.  */
 344 struct list
 345   {
 346     struct list *next;
 347     struct list *prev;
 348   };
 349
 350 /* Free list headers for each fragment size.  */
 351 extern struct list _fraghead[];
 352
 353 /* Instrumentation.  */
 354 extern size_t _chunks_used;
 355 extern size_t _bytes_used;
 356 extern size_t _chunks_free;
 357 extern size_t _bytes_free;
 358
 359 /* Internal version of free() used in morecore(). */
 360 extern void EXFUN(__free, (PTR __ptr));
 361
 362 #endif  /* _MALLOC_INTERNAL.  */
 363
 364 /* Underlying allocation function; successive calls should
 365    return contiguous pieces of memory.  */
 366 extern PTR EXFUN((*__morecore), (ptrdiff_t __size));
 367
 368 /* Default value of previous.  */
 369 extern PTR EXFUN(__default_morecore, (ptrdiff_t __size));
 370
 371 /* Flag whether malloc has been called.  */
 372 extern int __malloc_initialized;
 373
 374 /* Hooks for debugging versions.  */
 375 extern void EXFUN((*__free_hook), (PTR __ptr));
 376 extern PTR EXFUN((*__malloc_hook), (size_t __size));
 377 extern PTR EXFUN((*__realloc_hook), (PTR __ptr, size_t __size));
 378
 379 /* Activate a standard collection of debugging hooks.  */
 380 extern void EXFUN(mcheck, (void EXFUN((*func), (NOARGS))));
 381
 382 /* Statistics available to the user.  */
 383 struct mstats
 384   {
 385     size_t bytes_total;         /* Total size of the heap. */
 386     size_t chunks_used;         /* Chunks allocated by the user. */
 387     size_t bytes_used;          /* Byte total of user-allocated chunks. */
 388     size_t chunks_free;         /* Chunks in the free list. */
 389     size_t bytes_free;          /* Byte total of chunks in the free list. */
 390   };
 391
 392 /* Pick up the current statistics. */
 393 extern struct mstats EXFUN(mstats, (NOARGS));
 394
 395 #endif /* malloc.h  */
 396
 397 /* DO NOT DELETE THIS LINE -- free.c INSERTED HERE. */
 398 /* Free a block of memory allocated by `malloc'.
 399    Copyright 1990 Free Software Foundation
 400                   Written May 1989 by Mike Haertel.
 401
 402    The author may be reached (Email) at the address mike@ai.mit.edu,
 403    or (US mail) as Mike Haertel c/o Free Software Foundation.
 404
 405 This program is free software; you can redistribute it and/or modify
 406 it under the terms of the GNU General Public License as published by
 407 the Free Software Foundation; either version 2 of the License, or
 408 (at your option) any later version.
 409
 410 This program is distributed in the hope that it will be useful,
 411 but WITHOUT ANY WARRANTY; without even the implied warranty of
 412 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 413 GNU General Public License for more details.
 414
 415 You should have received a copy of the GNU General Public License
 416 along with this program; if not, write to the Free Software
 417 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
 418
 419 #ifndef __ONEFILE
 420 #include "ansidecl.h"
 421 #include <stddef.h>
 422 #include <stdlib.h>
 423
 424 #define _MALLOC_INTERNAL
 425 #include "malloc.h"
 426 #endif /* __ONEFILE */
 427
 428 /* Debugging hook for free.  */
 429 void EXFUN((*__free_hook), (PTR __ptr));
 430
 431 /* Return memory to the heap.  Like free() but don't call a __free_hook
 432    if there is one.  */
 433 void
 434 DEFUN(__free, (ptr), PTR ptr)
 435 {
 436   int type;
 437   size_t block, blocks;
 438   register size_t i;
 439   struct list *prev, *next;
 440
 441   block = BLOCK(ptr);
 442
 443   type = _heapinfo[block].busy.type;
 444   switch (type)
 445     {
 446     case 0:
 447       /* Get as many statistics as early as we can.  */
 448       --_chunks_used;
 449       _bytes_used -= _heapinfo[block].busy.info.size * BLOCKSIZE;
 450       _bytes_free += _heapinfo[block].busy.info.size * BLOCKSIZE;
 451
 452       /* Find the free cluster previous to this one in the free list.
 453          Start searching at the last block referenced; this may benefit
 454          programs with locality of allocation.  */
 455       i = _heapindex;
 456       if (i > block)
 457         while (i > block)
 458           i = _heapinfo[i].free.prev;
 459       else
 460         {
 461           do
 462             i = _heapinfo[i].free.next;
 463           while (i > 0 && i < block);
 464           i = _heapinfo[i].free.prev;
 465         }
 466
 467       /* Determine how to link this block into the free list.  */
 468       if (block == i + _heapinfo[i].free.size)
 469         {
 470           /* Coalesce this block with its predecessor.  */
 471           _heapinfo[i].free.size += _heapinfo[block].busy.info.size;
 472           block = i;
 473         }
 474       else
 475         {
 476           /* Really link this block back into the free list.  */
 477           _heapinfo[block].free.size = _heapinfo[block].busy.info.size;
 478           _heapinfo[block].free.next = _heapinfo[i].free.next;
 479           _heapinfo[block].free.prev = i;
 480           _heapinfo[i].free.next = block;
 481           _heapinfo[_heapinfo[block].free.next].free.prev = block;
 482           ++_chunks_free;
 483         }
 484
 485       /* Now that the block is linked in, see if we can coalesce it
 486          with its successor (by deleting its successor from the list
 487          and adding in its size).  */
 488       if (block + _heapinfo[block].free.size == _heapinfo[block].free.next)
 489         {
 490           _heapinfo[block].free.size
 491             += _heapinfo[_heapinfo[block].free.next].free.size;
 492           _heapinfo[block].free.next
 493             = _heapinfo[_heapinfo[block].free.next].free.next;
 494           _heapinfo[_heapinfo[block].free.next].free.prev = block;
 495           --_chunks_free;
 496         }
 497
 498       /* Now see if we can return stuff to the system.  */
 499       blocks = _heapinfo[block].free.size;
 500       if (blocks >= FINAL_FREE_BLOCKS && block + blocks == _heaplimit
 501           && (*__morecore)(0) == ADDRESS(block + blocks))
 502         {
 503           register size_t bytes = blocks * BLOCKSIZE;
 504           _heaplimit -= blocks;
 505           (*__morecore)(- bytes);
 506           _heapinfo[_heapinfo[block].free.prev].free.next
 507             = _heapinfo[block].free.next;
 508           _heapinfo[_heapinfo[block].free.next].free.prev
 509             = _heapinfo[block].free.prev;
 510           block = _heapinfo[block].free.prev;
 511           --_chunks_free;
 512           _bytes_free -= bytes;
 513         }
 514
 515       /* Set the next search to begin at this block.  */
 516       _heapindex = block;
 517       break;
 518
 519     default:
 520       /* Do some of the statistics.  */
 521       --_chunks_used;
 522       _bytes_used -= 1 << type;
 523       ++_chunks_free;
 524       _bytes_free += 1 << type;
 525
 526       /* Get the address of the first free fragment in this block.  */
 527       prev = (struct list *) ((char *) ADDRESS(block) +
 528                               (_heapinfo[block].busy.info.frag.first << type));
 529
 530       if (_heapinfo[block].busy.info.frag.nfree == (BLOCKSIZE >> type) - 1)
 531         {
 532           /* If all fragments of this block are free, remove them
 533              from the fragment list and free the whole block.  */
 534           next = prev;
 535           for (i = 1; i < BLOCKSIZE >> type; ++i)
 536             next = next->next;
 537           prev->prev->next = next;
 538           if (next != NULL)
 539             next->prev = prev->prev;
 540           _heapinfo[block].busy.type = 0;
 541           _heapinfo[block].busy.info.size = 1;
 542
 543           /* Keep the statistics accurate.  */
 544           ++_chunks_used;
 545           _bytes_used += BLOCKSIZE;
 546           _chunks_free -= BLOCKSIZE >> type;
 547           _bytes_free -= BLOCKSIZE;
 548
 549           free(ADDRESS(block));
 550         }
 551       else if (_heapinfo[block].busy.info.frag.nfree != 0)
 552         {
 553           /* If some fragments of this block are free, link this
 554              fragment into the fragment list after the first free
 555              fragment of this block. */
 556           next = (struct list *) ptr;
 557           next->next = prev->next;
 558           next->prev = prev;
 559           prev->next = next;
 560           if (next->next != NULL)
 561             next->next->prev = next;
 562           ++_heapinfo[block].busy.info.frag.nfree;
 563         }
 564       else
 565         {
 566           /* No fragments of this block are free, so link this
 567              fragment into the fragment list and announce that
 568              it is the first free fragment of this block. */
 569           prev = (struct list *) ptr;
 570           _heapinfo[block].busy.info.frag.nfree = 1;
 571           _heapinfo[block].busy.info.frag.first = RESIDUAL (ptr) >> type;
 572           prev->next = _fraghead[type].next;
 573           prev->prev = &_fraghead[type];
 574           prev->prev->next = prev;
 575           if (prev->next != NULL)
 576             prev->next->prev = prev;
 577         }
 578       break;
 579     }
 580 }
 581
 582 /* Return memory to the heap.  */
 583 void
 584 DEFUN(free, (ptr), PTR ptr)
 585 {
 586   if (ptr == NULL)
 587     return;
 588
 589   if (__free_hook != NULL)
 590     (*__free_hook)(ptr);
 591   else
 592     __free (ptr);
 593 }
 594
 595 /* DO NOT DELETE THIS LINE -- malloc.c INSERTED HERE. */
 596 /* Memory allocator `malloc'.
 597    Copyright 1990 Free Software Foundation
 598                   Written May 1989 by Mike Haertel.
 599
 600    The author may be reached (Email) at the address mike@ai.mit.edu,
 601    or (US mail) as Mike Haertel c/o Free Software Foundation.
 602
 603 This program is free software; you can redistribute it and/or modify
 604 it under the terms of the GNU General Public License as published by
 605 the Free Software Foundation; either version 2 of the License, or
 606 (at your option) any later version.
 607
 608 This program is distributed in the hope that it will be useful,
 609 but WITHOUT ANY WARRANTY; without even the implied warranty of
 610 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 611 GNU General Public License for more details.
 612
 613 You should have received a copy of the GNU General Public License
 614 along with this program; if not, write to the Free Software
 615 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
 616
 617 #ifndef __ONEFILE
 618 #include "ansidecl.h"
 619 #include <stddef.h>
 620 #include <stdlib.h>
 621 #include <string.h>
 622
 623 #define _MALLOC_INTERNAL
 624 #include "malloc.h"
 625 #endif /* __ONEFILE */
 626
 627 /* How to really get more memory.  */
 628 PTR EXFUN((*__morecore), (ptrdiff_t __size)) = __default_morecore;
 629
 630 /* Debugging hook for `malloc'.  */
 631 PTR EXFUN((*__malloc_hook), (size_t __size));
 632
 633 /* Pointer to the base of the first block.  */
 634 char *_heapbase;
 635
 636 /* Block information table.  Allocated with align/__free (not malloc/free).  */
 637 malloc_info *_heapinfo;
 638
 639 /* Number of info entries.  */
 640 static size_t heapsize;
 641
 642 /* Search index in the info table.  */
 643 size_t _heapindex;
 644
 645 /* Limit of valid info table indices.  */
 646 size_t _heaplimit;
 647
 648 /* Free lists for each fragment size.  */
 649 struct list _fraghead[BLOCKLOG];
 650
 651 /* Instrumentation.  */
 652 size_t _chunks_used;
 653 size_t _bytes_used;
 654 size_t _chunks_free;
 655 size_t _bytes_free;
 656
 657 /* Are you experienced?  */
 658 int __malloc_initialized;
 659
 660 /* Aligned allocation.  */
 661 static PTR
 662 DEFUN(align, (size), size_t size)
 663 {
 664   PTR result;
 665   unsigned int adj;
 666
 667   result = (*__morecore)(size);
 668   adj = RESIDUAL (result);
 669   if (adj != 0)
 670     {
 671       adj = BLOCKSIZE - adj;
 672       (void) (*__morecore)(adj);
 673       result = (char *) result + adj;
 674     }
 675   return result;
 676 }
 677
 678 /* Set everything up and remember that we have.  */
 679 static int
 680 DEFUN_VOID(initialize)
 681 {
 682   heapsize = HEAP / BLOCKSIZE;
 683   _heapinfo = (malloc_info *) align(heapsize * sizeof(malloc_info));
 684   if (_heapinfo == NULL)
 685     return 0;
 686   memset(_heapinfo, 0, heapsize * sizeof(malloc_info));
 687   _heapinfo[0].free.size = 0;
 688   _heapinfo[0].free.next = _heapinfo[0].free.prev = 0;
 689   _heapindex = 0;
 690   _heapbase = (char *) _heapinfo;
 691   __malloc_initialized = 1;
 692   return 1;
 693 }
 694
 695 /* Get neatly aligned memory, initializing or
 696    growing the heap info table as necessary. */
 697 static PTR
 698 DEFUN(morecore, (size), size_t size)
 699 {
 700   PTR result;
 701   malloc_info *newinfo, *oldinfo;
 702   size_t newsize;
 703
 704   result = align(size);
 705   if (result == NULL)
 706     return NULL;
 707
 708   /* Check if we need to grow the info table.  */
 709   if (BLOCK((char *) result + size) > heapsize)
 710     {
 711       newsize = heapsize;
 712       while (BLOCK((char *) result + size) > newsize)
 713         newsize *= 2;
 714       newinfo = (malloc_info *) align(newsize * sizeof(malloc_info));
 715       if (newinfo == NULL)
 716         {
 717           (*__morecore)(- size);
 718           return NULL;
 719         }
 720       memset(newinfo, 0, newsize * sizeof(malloc_info));
 721       memcpy(newinfo, _heapinfo, heapsize * sizeof(malloc_info));
 722       oldinfo = _heapinfo;
 723       newinfo[BLOCK(oldinfo)].busy.type = 0;
 724       newinfo[BLOCK(oldinfo)].busy.info.size
 725         = BLOCKIFY(heapsize * sizeof(malloc_info));
 726       _heapinfo = newinfo;
 727       __free(oldinfo);
 728       heapsize = newsize;
 729     }
 730
 731   _heaplimit = BLOCK((char *) result + size);
 732   return result;
 733 }
 734
 735 /* Allocate memory from the heap.  */
 736 PTR
 737 DEFUN(malloc, (size), size_t size)
 738 {
 739   PTR result;
 740   size_t block, blocks, lastblocks, start;
 741   register size_t i;
 742   struct list *next;
 743
 744   if (size == 0)
 745     return NULL;
 746
 747   if (__malloc_hook != NULL)
 748     return (*__malloc_hook)(size);
 749
 750   if (!__malloc_initialized)
 751     if (!initialize())
 752       return NULL;
 753
 754   if (size < sizeof(struct list))
 755     size = sizeof(struct list);
 756
 757   /* Determine the allocation policy based on the request size.  */
 758   if (size <= BLOCKSIZE / 2)
 759     {
 760       /* Small allocation to receive a fragment of a block.
 761          Determine the logarithm to base two of the fragment size. */
 762       register size_t log = 1;
 763       --size;
 764       while ((size /= 2) != 0)
 765         ++log;
 766
 767       /* Look in the fragment lists for a
 768          free fragment of the desired size. */
 769       next = _fraghead[log].next;
 770       if (next != NULL)
 771         {
 772           /* There are free fragments of this size.
 773              Pop a fragment out of the fragment list and return it.
 774              Update the block's nfree and first counters. */
 775           result = (PTR) next;
 776           next->prev->next = next->next;
 777           if (next->next != NULL)
 778             next->next->prev = next->prev;
 779           block = BLOCK(result);
 780           if (--_heapinfo[block].busy.info.frag.nfree != 0)
 781             _heapinfo[block].busy.info.frag.first =
 782               RESIDUAL (next->next) >> log;
 783
 784           /* Update the statistics.  */
 785           ++_chunks_used;
 786           _bytes_used += 1 << log;
 787           --_chunks_free;
 788           _bytes_free -= 1 << log;
 789         }
 790       else
 791         {
 792           /* No free fragments of the desired size, so get a new block
 793              and break it into fragments, returning the first.  */
 794           result = malloc(BLOCKSIZE);
 795           if (result == NULL)
 796             return NULL;
 797
 798           /* Link all fragments but the first into the free list.  */
 799           for (i = 1; i < BLOCKSIZE >> log; ++i)
 800             {
 801               next = (struct list *) ((char *) result + (i << log));
 802               next->next = _fraghead[log].next;
 803               next->prev = &_fraghead[log];
 804               next->prev->next = next;
 805               if (next->next != NULL)
 806                 next->next->prev = next;
 807             }
 808
 809           /* Initialize the nfree and first counters for this block.  */
 810           block = BLOCK(result);
 811           _heapinfo[block].busy.type = log;
 812           _heapinfo[block].busy.info.frag.nfree = i - 1;
 813           _heapinfo[block].busy.info.frag.first = i - 1;
 814
 815           _chunks_free += (BLOCKSIZE >> log) - 1;
 816           _bytes_free += BLOCKSIZE - (1 << log);
 817         }
 818     }
 819   else
 820     {
 821       /* Large allocation to receive one or more blocks.
 822          Search the free list in a circle starting at the last place visited.
 823          If we loop completely around without finding a large enough
 824          space we will have to get more memory from the system.  */
 825       blocks = BLOCKIFY(size);
 826       start = block = MALLOC_SEARCH_START;
 827       while (_heapinfo[block].free.size < blocks)
 828         {
 829           block = _heapinfo[block].free.next;
 830           if (block == start)
 831             {
 832               /* Need to get more from the system.  Check to see if
 833                  the new core will be contiguous with the final free
 834                  block; if so we don't need to get as much.  */
 835               block = _heapinfo[0].free.prev;
 836               lastblocks = _heapinfo[block].free.size;
 837               if (_heaplimit != 0 && block + lastblocks == _heaplimit &&
 838                   (*__morecore)(0) == ADDRESS(block + lastblocks) &&
 839                   (morecore((blocks - lastblocks) * BLOCKSIZE)) != NULL)
 840                 {
 841                   _heapinfo[block].free.size = blocks;
 842                   _bytes_free += (blocks - lastblocks) * BLOCKSIZE;
 843                   continue;
 844                 }
 845               result = morecore(blocks * BLOCKSIZE);
 846               if (result == NULL)
 847                 return NULL;
 848               block = BLOCK(result);
 849               _heapinfo[block].busy.type = 0;
 850               _heapinfo[block].busy.info.size = blocks;
 851               ++_chunks_used;
 852               _bytes_used += blocks * BLOCKSIZE;
 853               return result;
 854             }
 855         }
 856
 857       /* At this point we have found a suitable free list entry.
 858          Figure out how to remove what we need from the list. */
 859       result = ADDRESS(block);
 860       if (_heapinfo[block].free.size > blocks)
 861         {
 862           /* The block we found has a bit left over,
 863              so relink the tail end back into the free list. */
 864           _heapinfo[block + blocks].free.size
 865             = _heapinfo[block].free.size - blocks;
 866           _heapinfo[block + blocks].free.next
 867             = _heapinfo[block].free.next;
 868           _heapinfo[block + blocks].free.prev
 869             = _heapinfo[block].free.prev;
 870           _heapinfo[_heapinfo[block].free.prev].free.next
 871             = _heapinfo[_heapinfo[block].free.next].free.prev
 872               = _heapindex = block + blocks;
 873         }
 874       else
 875         {
 876           /* The block exactly matches our requirements,
 877              so just remove it from the list. */
 878           _heapinfo[_heapinfo[block].free.next].free.prev
 879             = _heapinfo[block].free.prev;
 880           _heapinfo[_heapinfo[block].free.prev].free.next
 881             = _heapindex = _heapinfo[block].free.next;
 882           --_chunks_free;
 883         }
 884
 885       _heapinfo[block].busy.type = 0;
 886       _heapinfo[block].busy.info.size = blocks;
 887       ++_chunks_used;
 888       _bytes_used += blocks * BLOCKSIZE;
 889       _bytes_free -= blocks * BLOCKSIZE;
 890     }
 891
 892   return result;
 893 }
 894
 895 /* DO NOT DELETE THIS LINE -- realloc.c INSERTED HERE. */
 896 /* Change the size of a block allocated by `malloc'.
 897    Copyright 1990 Free Software Foundation
 898                   Written May 1989 by Mike Haertel.
 899
 900    The author may be reached (Email) at the address mike@ai.mit.edu,
 901    or (US mail) as Mike Haertel c/o Free Software Foundation.
 902
 903 This program is free software; you can redistribute it and/or modify
 904 it under the terms of the GNU General Public License as published by
 905 the Free Software Foundation; either version 2 of the License, or
 906 (at your option) any later version.
 907
 908 This program is distributed in the hope that it will be useful,
 909 but WITHOUT ANY WARRANTY; without even the implied warranty of
 910 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 911 GNU General Public License for more details.
 912
 913 You should have received a copy of the GNU General Public License
 914 along with this program; if not, write to the Free Software
 915 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
 916
 917 #ifndef __ONEFILE
 918 #include "ansidecl.h"
 919 #include <stdlib.h>
 920 #include <string.h>
 921
 922 #define _MALLOC_INTERNAL
 923 #include "malloc.h"
 924 #endif /* __ONEFILE */
 925
 926 #define MIN(A, B) ((A) < (B) ? (A) : (B))
 927
 928 /* Debugging hook for realloc.  */
 929 PTR EXFUN((*__realloc_hook), (PTR __ptr, size_t __size));
 930
 931 /* Resize the given region to the new size, returning a pointer
 932    to the (possibly moved) region.  This is optimized for speed;
 933    some benchmarks seem to indicate that greater compactness is
 934    achieved by unconditionally allocating and copying to a
 935    new region.  This module has incestuous knowledge of the
 936    internals of both free and malloc. */
 937 PTR
 938 DEFUN(realloc, (ptr, size), PTR ptr AND size_t size)
 939 {
 940   PTR result;
 941   int type;
 942   size_t block, blocks, oldlimit;
 943
 944   if (size == 0)
 945     {
 946       free(ptr);
 947       return NULL;
 948     }
 949   else if (ptr == NULL)
 950     return malloc(size);
 951
 952   if (__realloc_hook != NULL)
 953     return (*__realloc_hook)(ptr, size);
 954
 955   block = BLOCK(ptr);
 956
 957   type = _heapinfo[block].busy.type;
 958   switch (type)
 959     {
 960     case 0:
 961       /* Maybe reallocate a large block to a small fragment.  */
 962       if (size <= BLOCKSIZE / 2)
 963         {
 964           result = malloc(size);
 965           if (result != NULL)
 966             {
 967               memcpy(result, ptr, size);
 968               free(ptr);
 969               return result;
 970             }
 971         }
 972
 973       /* The new size is a large allocation as well;
 974          see if we can hold it in place. */
 975       blocks = BLOCKIFY(size);
 976       if (blocks < _heapinfo[block].busy.info.size)
 977         {
 978           /* The new size is smaller; return
 979              excess memory to the free list. */
 980           _heapinfo[block + blocks].busy.type = 0;
 981           _heapinfo[block + blocks].busy.info.size
 982             = _heapinfo[block].busy.info.size - blocks;
 983           _heapinfo[block].busy.info.size = blocks;
 984           free(ADDRESS(block + blocks));
 985           result = ptr;
 986         }
 987       else if (blocks == _heapinfo[block].busy.info.size)
 988         /* No size change necessary.  */
 989         result = ptr;
 990       else
 991         {
 992           /* Won't fit, so allocate a new region that will.
 993              Free the old region first in case there is sufficient
 994              adjacent free space to grow without moving. */
 995           blocks = _heapinfo[block].busy.info.size;
 996           /* Prevent free from actually returning memory to the system.  */
 997           oldlimit = _heaplimit;
 998           _heaplimit = 0;
 999           free(ptr);
1000           _heaplimit = oldlimit;
1001           result = malloc(size);
1002           if (result == NULL)
1003             {
1004               (void) malloc(blocks * BLOCKSIZE);
1005               return NULL;
1006             }
1007           if (ptr != result)
1008             memmove(result, ptr, blocks * BLOCKSIZE);
1009         }
1010       break;
1011
1012     default:
1013       /* Old size is a fragment; type is logarithm
1014          to base two of the fragment size.  */
1015       if (size > 1 << (type - 1) && size <= 1 << type)
1016         /* The new size is the same kind of fragment.  */
1017         result = ptr;
1018       else
1019         {
1020           /* The new size is different; allocate a new space,
1021              and copy the lesser of the new size and the old. */
1022           result = malloc(size);
1023           if (result == NULL)
1024             return NULL;
1025           memcpy(result, ptr, MIN(size, 1 << type));
1026           free(ptr);
1027         }
1028       break;
1029     }
1030
1031   return result;
1032 }
1033
1034 /* DO NOT DELETE THIS LINE -- unix.c INSERTED HERE. */
1035 /* unix.c - get more memory with a UNIX system call.
1036    Copyright 1990 Free Software Foundation
1037                   Written May 1989 by Mike Haertel.
1038
1039    The author may be reached (Email) at the address mike@ai.mit.edu,
1040    or (US mail) as Mike Haertel c/o Free Software Foundation.
1041
1042 This program is free software; you can redistribute it and/or modify
1043 it under the terms of the GNU General Public License as published by
1044 the Free Software Foundation; either version 2 of the License, or
1045 (at your option) any later version.
1046
1047 This program is distributed in the hope that it will be useful,
1048 but WITHOUT ANY WARRANTY; without even the implied warranty of
1049 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
1050 GNU General Public License for more details.
1051
1052 You should have received a copy of the GNU General Public License
1053 along with this program; if not, write to the Free Software
1054 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
1055
1056 #ifndef __ONEFILE
1057 #include "ansidecl.h"
1058 #include <stddef.h>
1059
1060 #define _MALLOC_INTERNAL
1061 #include "malloc.h"
1062 #endif /* __ONEFILE */
1063
1064 extern PTR EXFUN(sbrk, (ptrdiff_t size));
1065
1066 PTR
1067 DEFUN(__default_morecore, (size), ptrdiff_t size)
1068 {
1069   PTR result;
1070
1071   result = sbrk(size);
1072   if (result == (PTR) -1)
1073     return NULL;
1074   return result;
1075 }
1076
1077 #define __getpagesize getpagesize
1078 /* DO NOT DELETE THIS LINE -- valloc.c INSERTED HERE. */
1079 /* Allocate memory on a page boundary.
1080    Copyright 1990 Free Software Foundation
1081                   Written May 1989 by Mike Haertel.
1082
1083    The author may be reached (Email) at the address mike@ai.mit.edu,
1084    or (US mail) as Mike Haertel c/o Free Software Foundation.
1085
1086 This program is free software; you can redistribute it and/or modify
1087 it under the terms of the GNU General Public License as published by
1088 the Free Software Foundation; either version 2 of the License, or
1089 (at your option) any later version.
1090
1091 This program is distributed in the hope that it will be useful,
1092 but WITHOUT ANY WARRANTY; without even the implied warranty of
1093 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
1094 GNU General Public License for more details.
1095
1096 You should have received a copy of the GNU General Public License
1097 along with this program; if not, write to the Free Software
1098 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
1099
1100 #ifndef __ONEFILE
1101 #include "ansidecl.h"
1102 #include <stdlib.h>
1103 #endif /* __ONEFILE */
1104
1105 #if defined(M_UNIX)
1106 /*
1107  * M_UNIX is defined by the SCO compilers, including the port of gcc.
1108  */
1109
1110 /* On SunOS 4.1.1, <sys/param.h> typedefs size_t, which is bad since
1111    we typedef it above.  Maybe it's better just to have people compile
1112    -Dgetpagesize()=4096.  */
1113 /* Deal with page size.  */
1114 #ifndef HAVE_GETPAGESIZE
1115
1116 #include <sys/param.h>
1117
1118 #if !defined (PAGESIZE)
1119 #ifdef EXEC_PAGESIZE
1120 #define PAGESIZE EXEC_PAGESIZE
1121 #else
1122 #ifdef NBPG
1123 #define PAGESIZE NBPG * CLSIZE
1124 #ifndef CLSIZE
1125 #define CLSIZE 1
1126 #endif /* no CLSIZE */
1127 #else /* no NBPG */
1128 #define PAGESIZE NBPC
1129 #endif /* no NBPG */
1130 #endif /* no EXEC_PAGESIZE */
1131 #endif /* no PAGESIZE */
1132
1133 size_t
1134 DEFUN_VOID(__getpagesize)
1135 {
1136   return PAGESIZE;
1137 }
1138 #endif /* not HAVE_GETPAGESIZE */
1139 #endif /* M_UNIX */
1140
1141 extern size_t EXFUN(__getpagesize, (NOARGS));
1142
1143 static size_t pagesize;
1144
1145 PTR
1146 DEFUN(valloc, (size), size_t size)
1147 {
1148   PTR result;
1149   unsigned int adj;
1150
1151   if (pagesize == 0)
1152     pagesize = __getpagesize();
1153
1154   result = malloc(size + pagesize);
1155   if (result == NULL)
1156     return NULL;
1157   adj = (unsigned int) ((unsigned int)((char *) result - (char *) NULL)) % pagesize;
1158   if (adj != 0)
1159     result = (char *) result + pagesize - adj;
1160   return result;
1161 }