binutils/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    This program is free software; you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10    the Free Software Foundation; either version 1, or (at your option)
  11    any later version.
  12
  13    This program is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program; if not, write to the Free Software
  20    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  21
  22    The author may be reached (Email) at the address mike@ai.mit.edu,
  23    or (US mail) as Mike Haertel c/o Free Software Foundation. */
  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 The GNU C Library 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 1, or (at your option)
  34 any later version.
  35
  36 The GNU C Library 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 the GNU C Library; see the file COPYING.  If not, write to
  43 the Free Software Foundation, 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, (void));
 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, 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    This program is free software; you can redistribute it and/or modify
 230    it under the terms of the GNU General Public License as published by
 231    the Free Software Foundation; either version 1, or (at your option)
 232    any later version.
 233
 234    This program is distributed in the hope that it will be useful,
 235    but WITHOUT ANY WARRANTY; without even the implied warranty of
 236    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 237    GNU General Public License for more details.
 238
 239    You should have received a copy of the GNU General Public License
 240    along with this program; if not, write to the Free Software
 241    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 242
 243    The author may be reached (Email) at the address mike@@ai.mit.edu,
 244    or (US mail) as Mike Haertel c/o Free Software Foundation. */
 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       (1 << BLOCKLOG)
 271 #define BLOCKIFY(SIZE)  (((SIZE) + BLOCKSIZE - 1) / BLOCKSIZE)
 272
 273 /* Determine the amount of memory spanned by the initial heap table
 274    (not an absolute limit).  */
 275 #define HEAP            (INT_BIT > 16 ? 4194304 : 65536)
 276
 277 /* Number of contiguous free blocks allowed to build up at the end of
 278    memory before they will be returned to the system.  */
 279 #define FINAL_FREE_BLOCKS       8
 280
 281 /* Where to start searching the free list when looking for new memory.
 282    The two possible values are 0 and _heapindex.  Starting at 0 seems
 283    to reduce total memory usage, while starting at _heapindex seems to
 284    run faster.  */
 285 #define MALLOC_SEARCH_START     _heapindex
 286
 287 /* Data structure giving per-block information.  */
 288 typedef union
 289   {
 290     /* Heap information for a busy block.  */
 291     struct
 292       {
 293         /* Zero for a large block, or positive giving the
 294            logarithm to the base two of the fragment size.  */
 295         int type;
 296         union
 297           {
 298             struct
 299               {
 300                 size_t nfree;   /* Free fragments in a fragmented block.  */
 301                 size_t first;   /* First free fragment of the block.  */
 302               } frag;
 303             /* Size (in blocks) of a large cluster.  */
 304             size_t size;
 305           } info;
 306       } busy;
 307     /* Heap information for a free block (that may be the first of
 308        a free cluster).  */
 309     struct
 310       {
 311         size_t size;            /* Size (in blocks) of a free cluster.  */
 312         size_t next;            /* Index of next free cluster.  */
 313         size_t prev;            /* Index of previous free cluster.  */
 314       } free;
 315   } malloc_info;
 316
 317 /* Pointer to first block of the heap.  */
 318 extern char *_heapbase;
 319
 320 /* Table indexed by block number giving per-block information.  */
 321 extern malloc_info *_heapinfo;
 322
 323 /* Address to block number and vice versa.  */
 324 #define BLOCK(A) (((char *) (A) - _heapbase) / BLOCKSIZE + 1)
 325 #define ADDRESS(B) ((PTR) (((B) - 1) * BLOCKSIZE + _heapbase))
 326
 327 /* Current search index for the heap table.  */
 328 extern size_t _heapindex;
 329
 330 /* Limit of valid info table indices.  */
 331 extern size_t _heaplimit;
 332
 333 /* Doubly linked lists of free fragments.  */
 334 struct list
 335   {
 336     struct list *next;
 337     struct list *prev;
 338   };
 339
 340 /* Free list headers for each fragment size.  */
 341 extern struct list _fraghead[];
 342
 343 /* Instrumentation.  */
 344 extern size_t _chunks_used;
 345 extern size_t _bytes_used;
 346 extern size_t _chunks_free;
 347 extern size_t _bytes_free;
 348
 349 /* Internal version of free() used in morecore(). */
 350 extern void EXFUN(__free, (PTR __ptr));
 351
 352 #endif  /* _MALLOC_INTERNAL.  */
 353
 354 /* Underlying allocation function; successive calls should
 355    return contiguous pieces of memory.  */
 356 extern PTR EXFUN((*__morecore), (ptrdiff_t __size));
 357
 358 /* Default value of previous.  */
 359 extern PTR EXFUN(__default_morecore, (ptrdiff_t __size));
 360
 361 /* Flag whether malloc has been called.  */
 362 extern int __malloc_initialized;
 363
 364 /* Hooks for debugging versions.  */
 365 extern void EXFUN((*__free_hook), (PTR __ptr));
 366 extern PTR EXFUN((*__malloc_hook), (size_t __size));
 367 extern PTR EXFUN((*__realloc_hook), (PTR __ptr, size_t __size));
 368
 369 /* Activate a standard collection of debugging hooks.  */
 370 extern void EXFUN(mcheck, (void EXFUN((*func), (void))));
 371
 372 /* Statistics available to the user.  */
 373 struct mstats
 374   {
 375     size_t bytes_total;         /* Total size of the heap. */
 376     size_t chunks_used;         /* Chunks allocated by the user. */
 377     size_t bytes_used;          /* Byte total of user-allocated chunks. */
 378     size_t chunks_free;         /* Chunks in the free list. */
 379     size_t bytes_free;          /* Byte total of chunks in the free list. */
 380   };
 381
 382 /* Pick up the current statistics. */
 383 extern struct mstats EXFUN(mstats, (NOARGS));
 384
 385 #endif /* malloc.h  */
 386
 387 /* DO NOT DELETE THIS LINE -- free.c INSERTED HERE. */
 388 /* Free a block of memory allocated by `malloc'.
 389    Copyright 1990 Free Software Foundation
 390                   Written May 1989 by Mike Haertel.
 391
 392    This program is free software; you can redistribute it and/or modify
 393    it under the terms of the GNU General Public License as published by
 394    the Free Software Foundation; either version 1, or (at your option)
 395    any later version.
 396
 397    This program is distributed in the hope that it will be useful,
 398    but WITHOUT ANY WARRANTY; without even the implied warranty of
 399    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 400    GNU General Public License for more details.
 401
 402    You should have received a copy of the GNU General Public License
 403    along with this program; if not, write to the Free Software
 404    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 405
 406    The author may be reached (Email) at the address mike@ai.mit.edu,
 407    or (US mail) as Mike Haertel c/o Free Software Foundation. */
 408
 409 #ifndef __ONEFILE
 410 #include "ansidecl.h"
 411 #include <stddef.h>
 412 #include <stdlib.h>
 413
 414 #define _MALLOC_INTERNAL
 415 #include "malloc.h"
 416 #endif /* __ONEFILE */
 417
 418 /* Debugging hook for free.  */
 419 void EXFUN((*__free_hook), (PTR __ptr));
 420
 421 /* Return memory to the heap.  Like free() but don't call a __free_hook
 422    if there is one.  */
 423 void
 424 DEFUN(__free, (ptr), PTR ptr)
 425 {
 426   int type;
 427   size_t block, blocks;
 428   register size_t i;
 429   struct list *prev, *next;
 430
 431   block = BLOCK(ptr);
 432
 433   type = _heapinfo[block].busy.type;
 434   switch (type)
 435     {
 436     case 0:
 437       /* Get as many statistics as early as we can.  */
 438       --_chunks_used;
 439       _bytes_used -= _heapinfo[block].busy.info.size * BLOCKSIZE;
 440       _bytes_free += _heapinfo[block].busy.info.size * BLOCKSIZE;
 441
 442       /* Find the free cluster previous to this one in the free list.
 443          Start searching at the last block referenced; this may benefit
 444          programs with locality of allocation.  */
 445       i = _heapindex;
 446       if (i > block)
 447         while (i > block)
 448           i = _heapinfo[i].free.prev;
 449       else
 450         {
 451           do
 452             i = _heapinfo[i].free.next;
 453           while (i > 0 && i < block);
 454           i = _heapinfo[i].free.prev;
 455         }
 456
 457       /* Determine how to link this block into the free list.  */
 458       if (block == i + _heapinfo[i].free.size)
 459         {
 460           /* Coalesce this block with its predecessor.  */
 461           _heapinfo[i].free.size += _heapinfo[block].busy.info.size;
 462           block = i;
 463         }
 464       else
 465         {
 466           /* Really link this block back into the free list.  */
 467           _heapinfo[block].free.size = _heapinfo[block].busy.info.size;
 468           _heapinfo[block].free.next = _heapinfo[i].free.next;
 469           _heapinfo[block].free.prev = i;
 470           _heapinfo[i].free.next = block;
 471           _heapinfo[_heapinfo[block].free.next].free.prev = block;
 472           ++_chunks_free;
 473         }
 474
 475       /* Now that the block is linked in, see if we can coalesce it
 476          with its successor (by deleting its successor from the list
 477          and adding in its size).  */
 478       if (block + _heapinfo[block].free.size == _heapinfo[block].free.next)
 479         {
 480           _heapinfo[block].free.size
 481             += _heapinfo[_heapinfo[block].free.next].free.size;
 482           _heapinfo[block].free.next
 483             = _heapinfo[_heapinfo[block].free.next].free.next;
 484           _heapinfo[_heapinfo[block].free.next].free.prev = block;
 485           --_chunks_free;
 486         }
 487
 488       /* Now see if we can return stuff to the system.  */
 489       blocks = _heapinfo[block].free.size;
 490       if (blocks >= FINAL_FREE_BLOCKS && block + blocks == _heaplimit
 491           && (*__morecore)(0) == ADDRESS(block + blocks))
 492         {
 493           register size_t bytes = blocks * BLOCKSIZE;
 494           _heaplimit -= blocks;
 495           (*__morecore)(- bytes);
 496           _heapinfo[_heapinfo[block].free.prev].free.next
 497             = _heapinfo[block].free.next;
 498           _heapinfo[_heapinfo[block].free.next].free.prev
 499             = _heapinfo[block].free.prev;
 500           block = _heapinfo[block].free.prev;
 501           --_chunks_free;
 502           _bytes_free -= bytes;
 503         }
 504
 505       /* Set the next search to begin at this block.  */
 506       _heapindex = block;
 507       break;
 508
 509     default:
 510       /* Do some of the statistics.  */
 511       --_chunks_used;
 512       _bytes_used -= 1 << type;
 513       ++_chunks_free;
 514       _bytes_free += 1 << type;
 515
 516       /* Get the address of the first free fragment in this block.  */
 517       prev = (struct list *) ((char *) ADDRESS(block) +
 518                               (_heapinfo[block].busy.info.frag.first << type));
 519
 520       if (_heapinfo[block].busy.info.frag.nfree == (BLOCKSIZE >> type) - 1)
 521         {
 522           /* If all fragments of this block are free, remove them
 523              from the fragment list and free the whole block.  */
 524           next = prev;
 525           for (i = 1; i < BLOCKSIZE >> type; ++i)
 526             next = next->next;
 527           prev->prev->next = next;
 528           if (next != NULL)
 529             next->prev = prev->prev;
 530           _heapinfo[block].busy.type = 0;
 531           _heapinfo[block].busy.info.size = 1;
 532
 533           /* Keep the statistics accurate.  */
 534           ++_chunks_used;
 535           _bytes_used += BLOCKSIZE;
 536           _chunks_free -= BLOCKSIZE >> type;
 537           _bytes_free -= BLOCKSIZE;
 538
 539           free(ADDRESS(block));
 540         }
 541       else if (_heapinfo[block].busy.info.frag.nfree != 0)
 542         {
 543           /* If some fragments of this block are free, link this
 544              fragment into the fragment list after the first free
 545              fragment of this block. */
 546           next = (struct list *) ptr;
 547           next->next = prev->next;
 548           next->prev = prev;
 549           prev->next = next;
 550           if (next->next != NULL)
 551             next->next->prev = next;
 552           ++_heapinfo[block].busy.info.frag.nfree;
 553         }
 554       else
 555         {
 556           /* No fragments of this block are free, so link this
 557              fragment into the fragment list and announce that
 558              it is the first free fragment of this block. */
 559           prev = (struct list *) ptr;
 560           _heapinfo[block].busy.info.frag.nfree = 1;
 561           _heapinfo[block].busy.info.frag.first = (unsigned int)
 562             (((char *) ptr - (char *) NULL) % BLOCKSIZE >> type);
 563           prev->next = _fraghead[type].next;
 564           prev->prev = &_fraghead[type];
 565           prev->prev->next = prev;
 566           if (prev->next != NULL)
 567             prev->next->prev = prev;
 568         }
 569       break;
 570     }
 571 }
 572
 573 /* Return memory to the heap.  */
 574 void
 575 DEFUN(free, (ptr), PTR ptr)
 576 {
 577   if (ptr == NULL)
 578     return;
 579
 580   if (__free_hook != NULL)
 581     (*__free_hook)(ptr);
 582   else
 583     __free (ptr);
 584 }
 585
 586 /* DO NOT DELETE THIS LINE -- malloc.c INSERTED HERE. */
 587 /* Memory allocator `malloc'.
 588    Copyright 1990 Free Software Foundation
 589                   Written May 1989 by Mike Haertel.
 590
 591    This program is free software; you can redistribute it and/or modify
 592    it under the terms of the GNU General Public License as published by
 593    the Free Software Foundation; either version 1, or (at your option)
 594    any later version.
 595
 596    This program is distributed in the hope that it will be useful,
 597    but WITHOUT ANY WARRANTY; without even the implied warranty of
 598    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 599    GNU General Public License for more details.
 600
 601    You should have received a copy of the GNU General Public License
 602    along with this program; if not, write to the Free Software
 603    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 604
 605    The author may be reached (Email) at the address mike@ai.mit.edu,
 606    or (US mail) as Mike Haertel c/o Free Software Foundation. */
 607
 608 #ifndef __ONEFILE
 609 #include "ansidecl.h"
 610 #include <stddef.h>
 611 #include <stdlib.h>
 612 #include <string.h>
 613
 614 #define _MALLOC_INTERNAL
 615 #include "malloc.h"
 616 #endif /* __ONEFILE */
 617
 618 /* How to really get more memory.  */
 619 PTR EXFUN((*__morecore), (ptrdiff_t __size)) = __default_morecore;
 620
 621 /* Debugging hook for `malloc'.  */
 622 PTR EXFUN((*__malloc_hook), (size_t __size));
 623
 624 /* Pointer to the base of the first block.  */
 625 char *_heapbase;
 626
 627 /* Block information table.  Allocated with align/__free (not malloc/free).  */
 628 malloc_info *_heapinfo;
 629
 630 /* Number of info entries.  */
 631 static size_t heapsize;
 632
 633 /* Search index in the info table.  */
 634 size_t _heapindex;
 635
 636 /* Limit of valid info table indices.  */
 637 size_t _heaplimit;
 638
 639 /* Free lists for each fragment size.  */
 640 struct list _fraghead[BLOCKLOG];
 641
 642 /* Instrumentation.  */
 643 size_t _chunks_used;
 644 size_t _bytes_used;
 645 size_t _chunks_free;
 646 size_t _bytes_free;
 647
 648 /* Are you experienced?  */
 649 int __malloc_initialized;
 650
 651 /* Aligned allocation.  */
 652 static PTR
 653 DEFUN(align, (size), size_t size)
 654 {
 655   PTR result;
 656   unsigned int adj;
 657
 658   result = (*__morecore)(size);
 659   adj = (unsigned int) ((char *) result - (char *) NULL) % BLOCKSIZE;
 660   if (adj != 0)
 661     {
 662       adj = BLOCKSIZE - adj;
 663       (void) (*__morecore)(adj);
 664       result = (char *) result + adj;
 665     }
 666   return result;
 667 }
 668
 669 /* Set everything up and remember that we have.  */
 670 static int
 671 DEFUN_VOID(initialize)
 672 {
 673   heapsize = HEAP / BLOCKSIZE;
 674   _heapinfo = (malloc_info *) align(heapsize * sizeof(malloc_info));
 675   if (_heapinfo == NULL)
 676     return 0;
 677   memset(_heapinfo, 0, heapsize * sizeof(malloc_info));
 678   _heapinfo[0].free.size = 0;
 679   _heapinfo[0].free.next = _heapinfo[0].free.prev = 0;
 680   _heapindex = 0;
 681   _heapbase = (char *) _heapinfo;
 682   __malloc_initialized = 1;
 683   return 1;
 684 }
 685
 686 /* Get neatly aligned memory, initializing or
 687    growing the heap info table as necessary. */
 688 static PTR
 689 DEFUN(morecore, (size), size_t size)
 690 {
 691   PTR result;
 692   malloc_info *newinfo, *oldinfo;
 693   size_t newsize;
 694
 695   result = align(size);
 696   if (result == NULL)
 697     return NULL;
 698
 699   /* Check if we need to grow the info table.  */
 700   if (BLOCK((char *) result + size) > heapsize)
 701     {
 702       newsize = heapsize;
 703       while (BLOCK((char *) result + size) > newsize)
 704         newsize *= 2;
 705       newinfo = (malloc_info *) align(newsize * sizeof(malloc_info));
 706       if (newinfo == NULL)
 707         {
 708           (*__morecore)(- size);
 709           return NULL;
 710         }
 711       memset(newinfo, 0, newsize * sizeof(malloc_info));
 712       memcpy(newinfo, _heapinfo, heapsize * sizeof(malloc_info));
 713       oldinfo = _heapinfo;
 714       newinfo[BLOCK(oldinfo)].busy.type = 0;
 715       newinfo[BLOCK(oldinfo)].busy.info.size
 716         = BLOCKIFY(heapsize * sizeof(malloc_info));
 717       _heapinfo = newinfo;
 718       __free(oldinfo);
 719       heapsize = newsize;
 720     }
 721
 722   _heaplimit = BLOCK((char *) result + size);
 723   return result;
 724 }
 725
 726 /* Allocate memory from the heap.  */
 727 PTR
 728 DEFUN(malloc, (size), size_t size)
 729 {
 730   PTR result;
 731   size_t block, blocks, lastblocks, start;
 732   register size_t i;
 733   struct list *next;
 734
 735   if (size == 0)
 736     return NULL;
 737
 738   if (__malloc_hook != NULL)
 739     return (*__malloc_hook)(size);
 740
 741   if (!__malloc_initialized)
 742     if (!initialize())
 743       return NULL;
 744
 745   if (size < sizeof(struct list))
 746     size = sizeof(struct list);
 747
 748   /* Determine the allocation policy based on the request size.  */
 749   if (size <= BLOCKSIZE / 2)
 750     {
 751       /* Small allocation to receive a fragment of a block.
 752          Determine the logarithm to base two of the fragment size. */
 753       register size_t log = 1;
 754       --size;
 755       while ((size /= 2) != 0)
 756         ++log;
 757
 758       /* Look in the fragment lists for a
 759          free fragment of the desired size. */
 760       next = _fraghead[log].next;
 761       if (next != NULL)
 762         {
 763           /* There are free fragments of this size.
 764              Pop a fragment out of the fragment list and return it.
 765              Update the block's nfree and first counters. */
 766           result = (PTR) next;
 767           next->prev->next = next->next;
 768           if (next->next != NULL)
 769             next->next->prev = next->prev;
 770           block = BLOCK(result);
 771           if (--_heapinfo[block].busy.info.frag.nfree != 0)
 772             _heapinfo[block].busy.info.frag.first = (unsigned int)
 773               (((char *) next->next - (char *) NULL) % BLOCKSIZE) >> log;
 774
 775           /* Update the statistics.  */
 776           ++_chunks_used;
 777           _bytes_used += 1 << log;
 778           --_chunks_free;
 779           _bytes_free -= 1 << log;
 780         }
 781       else
 782         {
 783           /* No free fragments of the desired size, so get a new block
 784              and break it into fragments, returning the first.  */
 785           result = malloc(BLOCKSIZE);
 786           if (result == NULL)
 787             return NULL;
 788
 789           /* Link all fragments but the first into the free list.  */
 790           for (i = 1; i < BLOCKSIZE >> log; ++i)
 791             {
 792               next = (struct list *) ((char *) result + (i << log));
 793               next->next = _fraghead[log].next;
 794               next->prev = &_fraghead[log];
 795               next->prev->next = next;
 796               if (next->next != NULL)
 797                 next->next->prev = next;
 798             }
 799
 800           /* Initialize the nfree and first counters for this block.  */
 801           block = BLOCK(result);
 802           _heapinfo[block].busy.type = log;
 803           _heapinfo[block].busy.info.frag.nfree = i - 1;
 804           _heapinfo[block].busy.info.frag.first = i - 1;
 805
 806           _chunks_free += (BLOCKSIZE >> log) - 1;
 807           _bytes_free += BLOCKSIZE - (1 << log);
 808         }
 809     }
 810   else
 811     {
 812       /* Large allocation to receive one or more blocks.
 813          Search the free list in a circle starting at the last place visited.
 814          If we loop completely around without finding a large enough
 815          space we will have to get more memory from the system.  */
 816       blocks = BLOCKIFY(size);
 817       start = block = MALLOC_SEARCH_START;
 818       while (_heapinfo[block].free.size < blocks)
 819         {
 820           block = _heapinfo[block].free.next;
 821           if (block == start)
 822             {
 823               /* Need to get more from the system.  Check to see if
 824                  the new core will be contiguous with the final free
 825                  block; if so we don't need to get as much.  */
 826               block = _heapinfo[0].free.prev;
 827               lastblocks = _heapinfo[block].free.size;
 828               if (_heaplimit != 0 && block + lastblocks == _heaplimit &&
 829                   (*__morecore)(0) == ADDRESS(block + lastblocks) &&
 830                   (morecore((blocks - lastblocks) * BLOCKSIZE)) != NULL)
 831                 {
 832                   _heapinfo[block].free.size = blocks;
 833                   _bytes_free += (blocks - lastblocks) * BLOCKSIZE;
 834                   continue;
 835                 }
 836               result = morecore(blocks * BLOCKSIZE);
 837               if (result == NULL)
 838                 return NULL;
 839               block = BLOCK(result);
 840               _heapinfo[block].busy.type = 0;
 841               _heapinfo[block].busy.info.size = blocks;
 842               ++_chunks_used;
 843               _bytes_used += blocks * BLOCKSIZE;
 844               return result;
 845             }
 846         }
 847
 848       /* At this point we have found a suitable free list entry.
 849          Figure out how to remove what we need from the list. */
 850       result = ADDRESS(block);
 851       if (_heapinfo[block].free.size > blocks)
 852         {
 853           /* The block we found has a bit left over,
 854              so relink the tail end back into the free list. */
 855           _heapinfo[block + blocks].free.size
 856             = _heapinfo[block].free.size - blocks;
 857           _heapinfo[block + blocks].free.next
 858             = _heapinfo[block].free.next;
 859           _heapinfo[block + blocks].free.prev
 860             = _heapinfo[block].free.prev;
 861           _heapinfo[_heapinfo[block].free.prev].free.next
 862             = _heapinfo[_heapinfo[block].free.next].free.prev
 863               = _heapindex = block + blocks;
 864         }
 865       else
 866         {
 867           /* The block exactly matches our requirements,
 868              so just remove it from the list. */
 869           _heapinfo[_heapinfo[block].free.next].free.prev
 870             = _heapinfo[block].free.prev;
 871           _heapinfo[_heapinfo[block].free.prev].free.next
 872             = _heapindex = _heapinfo[block].free.next;
 873           --_chunks_free;
 874         }
 875
 876       _heapinfo[block].busy.type = 0;
 877       _heapinfo[block].busy.info.size = blocks;
 878       ++_chunks_used;
 879       _bytes_used += blocks * BLOCKSIZE;
 880       _bytes_free -= blocks * BLOCKSIZE;
 881     }
 882
 883   return result;
 884 }
 885
 886 /* DO NOT DELETE THIS LINE -- realloc.c INSERTED HERE. */
 887 /* Change the size of a block allocated by `malloc'.
 888    Copyright 1990 Free Software Foundation
 889                   Written May 1989 by Mike Haertel.
 890
 891    This program is free software; you can redistribute it and/or modify
 892    it under the terms of the GNU General Public License as published by
 893    the Free Software Foundation; either version 1, or (at your option)
 894    any later version.
 895
 896    This program is distributed in the hope that it will be useful,
 897    but WITHOUT ANY WARRANTY; without even the implied warranty of
 898    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 899    GNU General Public License for more details.
 900
 901    You should have received a copy of the GNU General Public License
 902    along with this program; if not, write to the Free Software
 903    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 904
 905    The author may be reached (Email) at the address mike@ai.mit.edu,
 906    or (US mail) as Mike Haertel c/o Free Software Foundation. */
 907
 908 #ifndef __ONEFILE
 909 #include "ansidecl.h"
 910 #include <stdlib.h>
 911 #include <string.h>
 912
 913 #define _MALLOC_INTERNAL
 914 #include "malloc.h"
 915 #endif /* __ONEFILE */
 916
 917 #define MIN(A, B) ((A) < (B) ? (A) : (B))
 918
 919 /* Debugging hook for realloc.  */
 920 PTR EXFUN((*__realloc_hook), (PTR __ptr, size_t __size));
 921
 922 /* Resize the given region to the new size, returning a pointer
 923    to the (possibly moved) region.  This is optimized for speed;
 924    some benchmarks seem to indicate that greater compactness is
 925    achieved by unconditionally allocating and copying to a
 926    new region.  This module has incestuous knowledge of the
 927    internals of both free and malloc. */
 928 PTR
 929 DEFUN(realloc, (ptr, size), PTR ptr AND size_t size)
 930 {
 931   PTR result;
 932   int type;
 933   size_t block, blocks, oldlimit;
 934
 935   if (size == 0)
 936     {
 937       free(ptr);
 938       return NULL;
 939     }
 940   else if (ptr == NULL)
 941     return malloc(size);
 942
 943   if (__realloc_hook != NULL)
 944     return (*__realloc_hook)(ptr, size);
 945
 946   block = BLOCK(ptr);
 947
 948   type = _heapinfo[block].busy.type;
 949   switch (type)
 950     {
 951     case 0:
 952       /* Maybe reallocate a large block to a small fragment.  */
 953       if (size <= BLOCKSIZE / 2)
 954         {
 955           result = malloc(size);
 956           if (result != NULL)
 957             {
 958               memcpy(result, ptr, size);
 959               free(ptr);
 960               return result;
 961             }
 962         }
 963
 964       /* The new size is a large allocation as well;
 965          see if we can hold it in place. */
 966       blocks = BLOCKIFY(size);
 967       if (blocks < _heapinfo[block].busy.info.size)
 968         {
 969           /* The new size is smaller; return
 970              excess memory to the free list. */
 971           _heapinfo[block + blocks].busy.type = 0;
 972           _heapinfo[block + blocks].busy.info.size
 973             = _heapinfo[block].busy.info.size - blocks;
 974           _heapinfo[block].busy.info.size = blocks;
 975           free(ADDRESS(block + blocks));
 976           result = ptr;
 977         }
 978       else if (blocks == _heapinfo[block].busy.info.size)
 979         /* No size change necessary.  */
 980         result = ptr;
 981       else
 982         {
 983           /* Won't fit, so allocate a new region that will.
 984              Free the old region first in case there is sufficient
 985              adjacent free space to grow without moving. */
 986           blocks = _heapinfo[block].busy.info.size;
 987           /* Prevent free from actually returning memory to the system.  */
 988           oldlimit = _heaplimit;
 989           _heaplimit = 0;
 990           free(ptr);
 991           _heaplimit = oldlimit;
 992           result = malloc(size);
 993           if (result == NULL)
 994             {
 995               (void) malloc(blocks * BLOCKSIZE);
 996               return NULL;
 997             }
 998           if (ptr != result)
 999             memmove(result, ptr, blocks * BLOCKSIZE);
1000         }
1001       break;
1002
1003     default:
1004       /* Old size is a fragment; type is logarithm
1005          to base two of the fragment size.  */
1006       if (size > 1 << (type - 1) && size <= 1 << type)
1007         /* The new size is the same kind of fragment.  */
1008         result = ptr;
1009       else
1010         {
1011           /* The new size is different; allocate a new space,
1012              and copy the lesser of the new size and the old. */
1013           result = malloc(size);
1014           if (result == NULL)
1015             return NULL;
1016           memcpy(result, ptr, MIN(size, 1 << type));
1017           free(ptr);
1018         }
1019       break;
1020     }
1021
1022   return result;
1023 }
1024
1025 /* DO NOT DELETE THIS LINE -- unix.c INSERTED HERE. */
1026 /* unix.c - get more memory with a UNIX system call.
1027    Copyright 1990 Free Software Foundation
1028                   Written May 1989 by Mike Haertel.
1029
1030    This program is free software; you can redistribute it and/or modify
1031    it under the terms of the GNU General Public License as published by
1032    the Free Software Foundation; either version 1, or (at your option)
1033    any later version.
1034
1035    This program is distributed in the hope that it will be useful,
1036    but WITHOUT ANY WARRANTY; without even the implied warranty of
1037    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
1038    GNU General Public License for more details.
1039
1040    You should have received a copy of the GNU General Public License
1041    along with this program; if not, write to the Free Software
1042    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
1043
1044    The author may be reached (Email) at the address mike@ai.mit.edu,
1045    or (US mail) as Mike Haertel c/o Free Software Foundation. */
1046
1047 #ifndef __ONEFILE
1048 #include "ansidecl.h"
1049 #include <stddef.h>
1050
1051 #define _MALLOC_INTERNAL
1052 #include "malloc.h"
1053 #endif /* __ONEFILE */
1054
1055 extern PTR EXFUN(sbrk, (ptrdiff_t size));
1056
1057 PTR
1058 DEFUN(__default_morecore, (size), ptrdiff_t size)
1059 {
1060   PTR result;
1061
1062   result = sbrk(size);
1063   if (result == (PTR) -1)
1064     return NULL;
1065   return result;
1066 }
1067
1068 #define __getpagesize getpagesize
1069 /* DO NOT DELETE THIS LINE -- valloc.c INSERTED HERE. */
1070 /* Allocate memory on a page boundary.
1071    Copyright 1990 Free Software Foundation
1072                   Written May 1989 by Mike Haertel.
1073
1074    This program is free software; you can redistribute it and/or modify
1075    it under the terms of the GNU General Public License as published by
1076    the Free Software Foundation; either version 1, or (at your option)
1077    any later version.
1078
1079    This program is distributed in the hope that it will be useful,
1080    but WITHOUT ANY WARRANTY; without even the implied warranty of
1081    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
1082    GNU General Public License for more details.
1083
1084    You should have received a copy of the GNU General Public License
1085    along with this program; if not, write to the Free Software
1086    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
1087
1088    The author may be reached (Email) at the address mike@ai.mit.edu,
1089    or (US mail) as Mike Haertel c/o Free Software Foundation. */
1090
1091 #ifndef __ONEFILE
1092 #include "ansidecl.h"
1093 #include <stdlib.h>
1094 #endif /* __ONEFILE */
1095
1096 extern size_t EXFUN(__getpagesize, (NOARGS));
1097
1098 static size_t pagesize;
1099
1100 PTR
1101 DEFUN(valloc, (size), size_t size)
1102 {
1103   PTR result;
1104   unsigned int adj;
1105
1106   if (pagesize == 0)
1107     pagesize = __getpagesize();
1108
1109   result = malloc(size + pagesize);
1110   if (result == NULL)
1111     return NULL;
1112   adj = (unsigned int) ((char *) result - (char *) NULL) % pagesize;
1113   if (adj != 0)
1114     result = (char *) result + pagesize - adj;
1115   return result;
1116 }